Word Break Ii - Leetcode Solution

Problem Statement:

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"] Output: [   "cats and dog",   "cat sand dog" ]

Example 2:

Input: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] Output: [   "pine apple pen apple",   "pineapple pen apple",   "pine applepen apple" ] Explanation: Note that you are allowed to reuse a dictionary word.

Solution:

The problem can be solved using a recursive approach. We start iterating over the input string and keep on adding characters to the currentWord until we find a match in the word dictionary. As soon as we find a match, we add the currentWord to the result and start with the next character. We keep on doing this until we reach the end of the string. However, this approach can get very slow if the input string is very large, or if multiple valid sentences can be formed.

To optimize this approach, we will use dynamic programming. We store a boolean array of size n+1, where n is the length of the input string. dp[i] represents whether the string upto the i-th index can be segmented into words from the dictionary or not. We also store a hashmap of size n+1, where the key represents the index upto which we have already found valid solutions, and the value is a list of possible sentences.

We start by initializing dp[0] to be true, since an empty string is always a valid solution. Then we iterate over the string s and check if s[j:i] (where j is any index upto i) is a valid word from the dictionary, and if dp[j] is also true (meaning the string upto index j can be segmented into words). If both these conditions are met, we set dp[i] to be true and add the substring s[j:i] to the list of possible sentences at index i in the hashmap.

Finally, we recursively traverse the hashmap, starting from the last index, and build the valid sentences.

Here's the complete code:

class Solution { public List<String> wordBreak(String s, List<String> wordDict) { List<String> result = new ArrayList<>(); int n = s.length();

    // Create a hashmap to store possible sentences upto each index
    HashMap<Integer, List<String>> memo = new HashMap<>();
    memo.put(n, new ArrayList<>());
    memo.get(n).add("");
    
    // Create a boolean array to store whether the string upto an index can be segmented into words or not
    boolean[] dp = new boolean[n+1];
    dp[n] = true;
    
    // Populate the boolean array and hashmap
    for(int i=n-1; i>=0; i--) {
        List<String> list = new ArrayList<>();
        for(int j=i+1; j<=n; j++) {
            if(dp[j] && wordDict.contains(s.substring(i,j))) {
                dp[i] = true;
                if(memo.containsKey(j)) {
                    for(String str: memo.get(j)) {
                        list.add(s.substring(i,j) + (str.equals("") ? "" : " ") + str);
                    }
                }
            }
        }
        memo.put(i, list);
    }
    
    // Build valid sentences using hashmap
    return memo.get(0);
}

}

Time Complexity: O(n^2 * wordDict.length), where n is the length of the input string. We iterate over each index in the string n times, and for each index, we iterate over all possible substrings. We also need to check whether a string is present in the word dictionary, which takes O(wordDict.length) time.

Space Complexity: O(n^2), for the hashmap and boolean array.

1