Word Break II
Problem
Given a string s and a dictionary of words, add spaces to s to construct every sentence where each word is a valid dictionary word.
s = "catsanddog", dict = ["cat","cats","and","sand","dog"]["cats and dog","cat sand dog"]def word_break(s, word_dict):
words = set(word_dict)
memo = {}
def dfs(i):
if i in memo: return memo[i]
if i == len(s): return [""]
res = []
for j in range(i + 1, len(s) + 1):
piece = s[i:j]
if piece in words:
for tail in dfs(j):
res.append(piece if not tail else piece + " " + tail)
memo[i] = res
return res
return dfs(0)function wordBreak(s, wordDict) {
const words = new Set(wordDict);
const memo = new Map();
function dfs(i) {
if (memo.has(i)) return memo.get(i);
if (i === s.length) return [""];
const res = [];
for (let j = i + 1; j <= s.length; j++) {
const piece = s.slice(i, j);
if (words.has(piece)) {
for (const tail of dfs(j)) res.push(tail ? piece + " " + tail : piece);
}
}
memo.set(i, res);
return res;
}
return dfs(0);
}class Solution {
Set<String> words;
Map<Integer, List<String>> memo = new HashMap<>();
String s;
public List<String> wordBreak(String s, List<String> wordDict) {
this.s = s;
words = new HashSet<>(wordDict);
return dfs(0);
}
private List<String> dfs(int i) {
if (memo.containsKey(i)) return memo.get(i);
List<String> res = new ArrayList<>();
if (i == s.length()) { res.add(""); return res; }
for (int j = i + 1; j <= s.length(); j++) {
String piece = s.substring(i, j);
if (words.contains(piece))
for (String tail : dfs(j))
res.add(tail.isEmpty() ? piece : piece + " " + tail);
}
memo.put(i, res);
return res;
}
}class Solution {
unordered_set<string> words;
unordered_map<int, vector<string>> memo;
string s;
vector<string> dfs(int i) {
if (memo.count(i)) return memo[i];
vector<string> res;
if (i == (int)s.size()) { res.push_back(""); return res; }
for (int j = i + 1; j <= (int)s.size(); j++) {
string piece = s.substr(i, j - i);
if (words.count(piece))
for (auto& tail : dfs(j))
res.push_back(tail.empty() ? piece : piece + " " + tail);
}
memo[i] = res;
return res;
}
public:
vector<string> wordBreak(string s, vector<string>& dict) {
this->s = s;
words = {dict.begin(), dict.end()};
return dfs(0);
}
};Explanation
We want every way to split a string into spaced sequences of dictionary words. The natural approach is recursion: pick a first word, then solve the same problem for the rest of the string, and glue the pieces together.
The function dfs(i) answers the question "what are all sentences you can build from s starting at index i?" It tries every prefix s[i:j]; if that prefix is in the dictionary, it recursively asks for all sentences from j onward and prepends the prefix to each of them.
The base case is reaching the end of the string (i == len(s)), which returns a list with one empty string — the signal that there's exactly one way to finish: with nothing left.
The key efficiency trick is memoization with memo. Many different splits share the same suffix, so once we compute all sentences starting at a given index, we cache them and reuse the result instead of recomputing — this is what keeps the solution from blowing up on repetitive inputs.
Example: for "catsanddog", at index 0 both "cat" and "cats" match. Following "cats" leads to "and" then "dog", and following "cat" leads to "sand" then "dog", giving the two sentences "cats and dog" and "cat sand dog".