140. Word Break II

Hard

Problem Description

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.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Examples

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"]

Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def wordBreak(s: str, wordDict: List[str]) -> List[str]:
    def backtrack(start: int, memo: Dict[int, List[str]]) -> List[str]:
        if start in memo:
            return memo[start]
        
        result = []
        if start == len(s):
            result.append("")
            return result
        
        for word in wordDict:
            if s.startswith(word, start):
                sub_sentences = backtrack(start + len(word), memo)
                for sub in sub_sentences:
                    result.append((word + " " + sub).strip())
        
        memo[start] = result
        return result
    
    return backtrack(0, {})

Java Solution


class Solution {
    private Map> memo;
    private String s;
    private List wordDict;
    
    public List wordBreak(String s, List wordDict) {
        this.memo = new HashMap<>();
        this.s = s;
        this.wordDict = wordDict;
        return backtrack(0);
    }
    
    private List backtrack(int start) {
        if (memo.containsKey(start)) {
            return memo.get(start);
        }
        
        List result = new ArrayList<>();
        if (start == s.length()) {
            result.add("");
            return result;
        }
        
        for (String word : wordDict) {
            if (s.startsWith(word, start)) {
                List subSentences = backtrack(start + word.length());
                for (String sub : subSentences) {
                    result.add((word + (sub.isEmpty() ? "" : " " + sub)));
                }
            }
        }
        
        memo.put(start, result);
        return result;
    }
}

C++ Solution


class Solution {
private:
    unordered_map> memo;
    string s;
    vector wordDict;
    
    vector backtrack(int start) {
        if (memo.count(start)) {
            return memo[start];
        }
        
        vector result;
        if (start == s.length()) {
            result.push_back("");
            return result;
        }
        
        for (const string& word : wordDict) {
            if (s.compare(start, word.length(), word) == 0) {
                vector subSentences = backtrack(start + word.length());
                for (const string& sub : subSentences) {
                    result.push_back(word + (sub.empty() ? "" : " " + sub));
                }
            }
        }
        
        memo[start] = result;
        return result;
    }
    
public:
    vector wordBreak(string s, vector& wordDict) {
        this->s = s;
        this->wordDict = wordDict;
        return backtrack(0);
    }
};

JavaScript Solution


/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {string[]}
 */
var wordBreak = function(s, wordDict) {
    const memo = new Map();
    
    const backtrack = (start) => {
        if (memo.has(start)) {
            return memo.get(start);
        }
        
        const result = [];
        if (start === s.length) {
            result.push("");
            return result;
        }
        
        for (const word of wordDict) {
            if (s.startsWith(word, start)) {
                const subSentences = backtrack(start + word.length);
                for (const sub of subSentences) {
                    result.push(word + (sub ? " " + sub : ""));
                }
            }
        }
        
        memo.set(start, result);
        return result;
    };
    
    return backtrack(0);
};

C# Solution


public class Solution {
    private Dictionary> memo;
    private string s;
    private IList wordDict;
    
    public IList WordBreak(string s, IList wordDict) {
        this.memo = new Dictionary>();
        this.s = s;
        this.wordDict = wordDict;
        return Backtrack(0);
    }
    
    private IList Backtrack(int start) {
        if (memo.ContainsKey(start)) {
            return memo[start];
        }
        
        var result = new List();
        if (start == s.Length) {
            result.Add("");
            return result;
        }
        
        foreach (string word in wordDict) {
            if (s.Length - start >= word.Length && 
                s.Substring(start, word.Length) == word) {
                var subSentences = Backtrack(start + word.Length);
                foreach (var sub in subSentences) {
                    result.Add(word + (string.IsNullOrEmpty(sub) ? "" : " " + sub));
                }
            }
        }
        
        memo[start] = result;
        return result;
    }
}

Complexity Analysis

Solution Explanation

This solution uses backtracking with memoization:

Key points: