LeetCode 140: Word Break II

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.

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);
            }
        }
    }
}