MANG Problem #32: Word Break II (Hard)

1. Problem Statement

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

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

2. Approach: DFS with Memoization

A pure backtracking approach will Time Out ($O(2^N)$). We need to memoize the results of suffixes.

1. State: map.get(s) returns the list of valid sentences that can be formed from string s.
2. Recursion:
   • For a string s, check if it starts with any word in the dictionary.
   • If it does, recursively call the function on the remainder of the string.
   • Append the current word to all sentences returned by the recursive call.
3. Memoization: Store the result for s in a HashMap.

3. Java Implementation

public List<String> wordBreak(String s, List<String> wordDict) {
    return dfs(s, new HashSet<>(wordDict), new HashMap<String, List<String>>());
}

private List<String> dfs(String s, Set<String> wordDict, Map<String, List<String>> map) {
    if (map.containsKey(s)) return map.get(s);
    
    List<String> res = new ArrayList<>();
    if (s.isEmpty()) {
        res.add("");
        return res;
    }
    
    for (String word : wordDict) {
        if (s.startsWith(word)) {
            String sub = s.substring(word.length());
            List<String> subList = dfs(sub, wordDict, map);
            for (String subSentence : subList) {
                res.add(word + (subSentence.isEmpty() ? "" : " ") + subSentence);
            }
        }
    }
    map.put(s, res);
    return res;
}

4. 5-Minute "Video-Style" Walkthrough

1. The "Aha!" Moment: If "sanddog" can be broken into ["sand dog"], then when processing "cat", we just prepend "cat " to all the results of "sanddog".
2. The Memoization Map: The map stores String -> List<String>. If we've already figured out how to break "dog", we don't compute it again. We just return ["dog"].
3. The Empty String Base Case: When s.isEmpty(), returning [""] is critical. It allows the final word in the string to append itself without an extra trailing space.

5. Interview Discussion

• Interviewer: "What is the time complexity?"
• You: "In the worst case (e.g., s = aaaaab, dict = [a, aa, aaa]), it is $O(2^N)$ because there are exponential valid sentences. But memoization drastically prunes branches that lead to invalid words."
• Interviewer: "Can we use a Trie?"
• You: "Yes! Instead of s.startsWith(word), we can traverse a Trie built from wordDict. This avoids creating multiple substrings and is faster when the dictionary is large."