D
DevExCode

LeetCode 140: Word Break II Solution

Master LeetCode problem 140 (Word Break II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming along with backtracking. We will first check if the input string can be segmented using the words in the dictionary. Then, we will find all possible sentences by backtracking through the segmented words.

  1. Dynamic Programming:

    • We will use a boolean array dp[] of size n+1 where n is the length of the input string s. dp[i] will be true if the substring s[0:i] can be segmented using the words in the dictionary.
    • We will initialize dp[0] as true to indicate an empty string can be segmented.
    • We will iterate through each index i from 1 to n and check if there exists an index j such that dp[j] is true and s.substring(j, i) is in the dictionary. If both conditions are met, we will set dp[i] as true.

  2. Backtracking:

    • After finding all possible segmented positions using dynamic programming, we will perform backtracking to construct all valid sentences.
    • We will maintain a list of strings result to store all valid sentences.
    • Starting from the end of the input string, we will backtrack through the segmented positions to construct each valid sentence.
    • We will recursively explore all possible combinations of words from the dictionary to form valid sentences.

  3. Time Complexity:

    • The time complexity of this approach is O(n^2 * m) where n is the length of the input string s and m is the average length of words in the dictionary.

  4. Space Complexity:

    • The space complexity is O(n) for the boolean array dp and O(n * m) for the backtracking stack.

Solution Code

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> result = new ArrayList<>();
        Set<String> dict = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        if (dp[n]) {
            backtrack(s, n, dict, new ArrayList<>(), result);
        }
        return result;
    }
    
    private void backtrack(String s, int end, Set<String> dict, List<String> path, List<String> result) {
        if (end == 0) {
            result.add(String.join(" ", path));
            return;
        }
        for (int i = end - 1; i >= 0; i--) {
            String word = s.substring(i, end);
            if (dict.contains(word)) {
                path.add(0, word);
                backtrack(s, i, dict, path, result);
                path.remove(0);
            }
        }
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 140 (Word Break II)?

This page provides optimized solutions for LeetCode problem 140 (Word Break II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 140 (Word Break II)?

The time complexity for LeetCode 140 (Word Break II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 140 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 140 in Java, C++, or Python.

Back to LeetCode Solutions