The problem. Given a string s and a list of words wordDict, return true if s can be cut into a sequence of one or more dictionary words. A word may be used any number of times.
![s equals applepenapple, with the dictionary apple and pen. Under the letters is the dp row, one cell for each cut position from 0 to 13. dp[0] is true for the empty prefix. dp[5] is true because apple follows it, dp[8] because pen follows dp[5], and dp[13], the whole string, because apple follows dp[8]. Every other cell is false.](/drawings/53d4b1ae-d1eb-41a6-b190-6773894ba454.svg)
s = "leetcode", wordDict = ["leet", "code"] -> true ("leet code")
s = "applepenapple", wordDict = ["apple", "pen"] -> true ("apple pen apple")
s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] -> falseCutting the string one word at a time and trying every word is a search with many repeated questions: in "catsandog", both "cats" + "and" and "cat" + "sand" end up asking whether "og" can be split. So ask the question once per prefix instead.
The first i letters can be split exactly when some shorter prefix can be split and the letters after it, s[j..i), form one word. That's a one-string DP: dp[i] for the first i letters, with dp[0] = true (the empty prefix needs no words) and the answer in dp[n]. The last word is at most as long as the longest dictionary word, L, so only the last L cut points need checking.
function wordBreak(s, wordDict) { const canSplit = (start) => { // can s[start..] be split? if (start === s.length) return true; for (const w of wordDict) { if (s.startsWith(w, start) && canSplit(start + w.length)) return true; } return false; }; return canSplit(0);}Time O(2ⁿ) in the worst case, space O(n) for the call stack. With s = "aaaa…ab" and the words "a", "aa", "aaa", every way of cutting up the a's is tried before the b makes each one fail. But there are only n + 1 different starts, so remember each answer.
function wordBreak(s, wordDict) { const memo = new Map(); // start -> can s[start..] be split? const canSplit = (start) => { if (start === s.length) return true; if (memo.has(start)) return memo.get(start); let ok = false; for (const w of wordDict) { if (s.startsWith(w, start) && canSplit(start + w.length)) { ok = true; break; } } memo.set(start, ok); return ok; }; return canSplit(0);}Time O(n · D · L), space O(n) for n starts, D words of length up to L. A start that failed once is never explored again, so "aaaa…ab" is no longer a problem. The table below is the same idea filled from the other end: prefixes instead of suffixes.
dp[i] is true when some true dp[j] is followed by a dictionary word s[j..i).
function wordBreak(s, wordDict) { const words = new Set(wordDict); const longest = Math.max(...wordDict.map((w) => w.length)); // dp[i]: can the first i letters, s[0..i), be split into dictionary words? const dp = new Array(s.length + 1).fill(false); dp[0] = true; // the empty prefix needs no words for (let i = 1; i <= s.length; i++) { for (let j = Math.max(0, i - longest); j < i; j++) { if (dp[j] && words.has(s.slice(j, i))) { // a good split up to j, then one word dp[i] = true; break; } } } return dp[s.length];}Time O(n · L²), space O(n + D), where L is the longest word and D the total size of the dictionary. Each of the n prefixes tries at most L cut points, and each try slices and hashes up to L letters.
The DP is the expected answer. Explaining why recursion is slow — the same suffix asked about again and again — is what shows you understand why DP is the right tool.
"aaaa" with ["a"] is true."goalspecial" with ["go", "goal", "goals", "special"]: taking the longest word first, "goals", leaves "pecial"; the DP finds "goal" + "special"."catsandog" splits up to "og" and no further: false.dp[n] comes straight from dp[0].dp[i] looks back at earlier cut points j. First lesson of this pattern.