0
start
Return every sentence formed by inserting spaces so each piece is a dictionary word. Backtrack from index start, trying each dictionary prefix, and memoize start → all suffix-sentences so the recursion never re-solves a position twice.
Given s = "catsanddog" and wordDict = ["cat", "cats", "and", "sand", "dog"], return every way to break s into a sentence of dictionary words: ["cats and dog", "cat sand dog"].
Word Break I only asked can it be segmented (a boolean). Word Break II asks for the actual list of sentences, so we must reconstruct and join the splits, not just answer yes/no. Words may be reused, and the output can be empty if no segmentation exists.
dfs(start) return all sentences that segment the suffix s[start..). For each dictionary word starting at start and ending at end, recurse on dfs(end) and prefix the word onto every sentence it returns. The base case dfs(n) returns [""] (one empty sentence) so the very last word has something to attach to. Cache start → sentences[] so each index is expanded once and its list is reused everywhere it appears.wordDict into a Set for O(1) membership tests, and a memo: Map<number, string[]>.dfs(n) returns [""] — the empty suffix has exactly one segmentation, the empty sentence. (Returning [] here would wrongly kill every branch.)start is cached, return the stored list immediately — this is what tames the exponential.end from start+1 to n, take word = s[start..end). Skip it unless it's in the dictionary.rest in dfs(end), push word if rest is empty, else word + " " + rest.start and return them. The answer is dfs(0).boolean[] table without extra work — you must store (or rebuild) the actual word listsand concatenate them. That's why the memo value here is string[], not boolean."aaaa…" blow up exponentially.The memo guarantees each start is computed once, so the work to find the segmentations is polynomial. But the number of sentences can be exponential (e.g. every prefix splittable many ways), and we must list them all — so any correct solution is exponential in the worst case. Memoization removes the redundant recomputation, which is the difference between "times out" and "passes" on adversarial inputs.
dict as a Set and an empty memo. Kick off dfs(0) to segment all of "catsanddog".1function wordBreak(s: string, wordDict: string[]): string[] {2▶ const dict = new Set(wordDict);3 // memo: start index -> every sentence that segments s[start..)4▶ const memo = new Map<number, string[]>();56 function dfs(start: number): string[] {7 if (start === s.length) return ['']; // empty suffix -> one empty sentence8 const cached = memo.get(start);9 if (cached !== undefined) return cached;1011 const sentences: string[] = [];12 for (let end = start + 1; end <= s.length; end++) {13 const word = s.slice(start, end);14 if (!dict.has(word)) continue; // not a dictionary prefix15 for (const rest of dfs(end)) { // all ways to break the suffix16 sentences.push(rest === '' ? word : word + ' ' + rest);17 }18 }1920 memo.set(start, sentences);21 return sentences;22 }2324▶ return dfs(0);25}
function wordBreak(s: string, wordDict: string[]): string[] {
const dict = new Set(wordDict);
// memo: start index -> every sentence that segments s[start..)
const memo = new Map<number, string[]>();
function dfs(start: number): string[] {
if (start === s.length) return ['']; // empty suffix -> one empty sentence
const cached = memo.get(start);
if (cached !== undefined) return cached;
const sentences: string[] = [];
for (let end = start + 1; end <= s.length; end++) {
const word = s.slice(start, end);
if (!dict.has(word)) continue; // not a dictionary prefix
for (const rest of dfs(end)) { // all ways to break the suffix
sentences.push(rest === '' ? word : word + ' ' + rest);
}
}
memo.set(start, sentences);
return sentences;
}
return dfs(0);
}Set gives O(1) has() checks. The memomaps a start index to the full list of sentences that segment the suffix beginning there — that's the cache that prevents exponential recomputation.start === s.lengthwe've consumed the whole string, so the suffix is empty. It has exactly one segmentation — the empty sentence — so we return ['']. Returning [] here would make every branch collapse to no results.start, return the cached list. Because each index can be reached from many earlier splits, this reuse is what keeps the algorithm from blowing up.end forward; the candidate word = s.slice(start, end). Skip non-dictionary slices. For each valid word, recurse on dfs(end) to get every way the rest can be broken, and stitch word in front of each — adding a space only when restisn't the empty sentence.start and hand them back. The top-level call dfs(0) returns every sentence for the entire string.n+1 start indices is expanded at most once thanks to the memo, and at each we scan O(n) end positions with O(n) slice/join work, so finding the splits is polynomial. The dominating cost is the output: there can be exponentially many sentences (worst case O(n · 2ⁿ) characters), so the overall bound is exponential — O(n² · 2ⁿ) — driven by how many sentences exist, not by wasted recomputation.false, return [] instantly instead of exploring a doomed tree. You can also only recurse into positions reachable from the start.sentences[i] for i from n down to 0 — same idea, same complexity."aaaa" with ["a","aa","aaa"]). No algorithm can beat that lower bound since it must produce every answer.has() with a trie so you extend from start character-by-character and stop early when no word continues.function wordBreak(s: string, wordDict: string[]): string[] {
const dict = new Set(wordDict);
// memo: start index -> every sentence that segments s[start..)
const memo = new Map<number, string[]>();
function dfs(start: number): string[] {
if (start === s.length) return ['']; // empty suffix -> one empty sentence
const cached = memo.get(start);
if (cached !== undefined) return cached;
const sentences: string[] = [];
for (let end = start + 1; end <= s.length; end++) {
const word = s.slice(start, end);
if (!dict.has(word)) continue; // not a dictionary prefix
for (const rest of dfs(end)) { // all ways to break the suffix
sentences.push(rest === '' ? word : word + ' ' + rest);
}
}
memo.set(start, sentences);
return sentences;
}
return dfs(0);
}n+1 start indices is expanded at most once thanks to the memo, and at each we scan O(n) end positions with O(n) slice/join work, so finding the splits is polynomial. The dominating cost is the output: there can be exponentially many sentences (worst case O(n · 2ⁿ) characters), so the overall bound is exponential — O(n² · 2ⁿ) — driven by how many sentences exist, not by wasted recomputation.Fill dp[i] = every sentence for the suffix s[i..), iterating i from n down to 0 so each suffix is already solved before you reach it.
function wordBreak(s: string, wordDict: string[]): string[] {
const dict = new Set(wordDict);
const n = s.length;
// dp[i] = every sentence that segments the suffix s[i..)
const dp: string[][] = new Array(n + 1);
dp[n] = ['']; // base: empty suffix has one segmentation, the empty sentence
for (let start = n - 1; start >= 0; start--) {
const sentences: string[] = [];
for (let end = start + 1; end <= n; end++) {
const word = s.slice(start, end);
if (!dict.has(word)) continue; // not a dictionary prefix
for (const rest of dp[end]) { // already-computed suffix sentences
sentences.push(rest === '' ? word : word + ' ' + rest);
}
}
dp[start] = sentences;
}
return dp[0];
}dp[end] is always filled before dp[start], the inner loop only ever reads completed lists. No memo bookkeeping and no recursion depth, at the cost of materializing every suffix's sentence list eagerly.Carry the words chosen so far down the recursion and record a finished sentence each time you reach the end — simple, but re-explores shared suffixes from scratch.
function wordBreak(s: string, wordDict: string[]): string[] {
const dict = new Set(wordDict);
const n = s.length;
const result: string[] = [];
const path: string[] = []; // dictionary words chosen so far
function dfs(start: number): void {
if (start === n) { // consumed the whole string
result.push(path.join(' '));
return;
}
for (let end = start + 1; end <= n; end++) {
const word = s.slice(start, end);
if (!dict.has(word)) continue;
path.push(word); // choose
dfs(end); // explore the rest
path.pop(); // un-choose (backtrack)
}
}
dfs(0);
return result;
}s = "aaaaaaaaaaaaaaab" with dict = ["a","aa","aaa"] (no valid full split) explode to O(2ⁿ) dead-end exploration and time out. The memoized solution adds a start → string[] cache to kill exactly that redundant recomputation.| "return ALL ways to segment / partition" | DFS returning lists, not a boolean |
| reconstruct sentences from a word dictionary | memo: start -> string[] of suffixes |
| overlapping suffixes re-solved | memoize the start index |
| empty suffix must still produce a result | base case returns [''] |
function wordBreak(s: string, wordDict: string[]): string[] {
const dict = new Set(wordDict);
const memo = new Map<number, string[]>();
function dfs(start: number): string[] {
if (start === s.length) return ['']; // base: one empty sentence
if (memo.has(start)) return memo.get(start)!;
const out: string[] = [];
for (let end = start + 1; end <= s.length; end++) {
const word = s.slice(start, end);
if (!dict.has(word)) continue;
for (const rest of dfs(end)) // join word + suffix sentences
out.push(rest === '' ? word : word + ' ' + rest);
}
memo.set(start, out);
return out;
}
return dfs(0);
}dfs(start) return in Word Break II?s[start..).dfs(start) return in the memoized Word Break II solution?dfs(s.length) return [''] rather than []?s="catsanddog" and dict=["cat","cats","and","sand","dog"], how many sentences are returned?boolean[] DP table (as in Word Break I) not enough for Word Break II?s="aaaaaaaa" with dict=["a","aa","aaa"], the number of returned sentences grows:word in front of a suffix sentence rest, when do you omit the joining space?