true
dp[0]
Build a boolean DP table where dp[i] asks “can s[0..i) be segmented into dictionary words?” — seeding dp[0] = true and propagating forward with a nested split loop.
Given a string s and a list of words wordDict, return true if s can be split into a sequence of one or more dictionary words. Words may be reused.
Example: s = "leetcode", wordDict = ["leet", "code"] → true because "leet" + "code" covers the whole string. But s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] → false: no partition reaches the end.
dp[i] = “the first i characters of sare segmentable.” Then dp[i] is true iff there exists some split point j < i where both dp[j] is true (the prefix up to j is already solved) and s[j..i) is a dictionary word. The empty prefix dp[0] = true is the seed that starts the chain.dp[0] = true. The empty string needs no words — this anchors everything.i = 1..n. We're asking: can s[0..i) be segmented?j = 0..i-1. Try every split point. If dp[j] is already true, the prefix to j is safe — we only need s[j..i) to be a word.dp[j] && dict.has(s.slice(j, i)), set dp[i] = true and break — one valid split is enough.dp[n].dp[0] = false and wonder why nothing propagates. The empty prefix dp[0] = trueisn't an edge case — it's the indispensable seed. Without it, even a single-word string like "leet" would return false.Memoized DFS: same O(n²) complexity; top-down instead of bottom-up, which some find more natural to write. Trie: replace the hash set with a trie over the dict to speed up repeated prefix lookups — helpful when |wordDict| is huge but word lengths are short. The DP approach is the cleanest for interviews.
dp[0] = true — the empty prefix is always segmentable. We'll fill dp[1..8] left to right.function wordBreak(s: string, wordDict: string[]): boolean {
const dict = new Set(wordDict);
const n = s.length;
const dp: boolean[] = new Array(n + 1).fill(false);
dp[0] = true; // empty prefix is always segmentable
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && dict.has(s.slice(j, i))) {
dp[i] = true;
break; // one valid split is enough
}
}
}
return dp[n];
}Set gives O(1) average lookup for dict.has(word). Using the raw array would be O(w) per lookup and degrade the overall complexity.dp is length n + 1 so index i directly represents the first i characters. Setting dp[0] = true expresses: the empty string needs zero words — always segmentable. This seed is what lets the first real word propagate.i, scan every split point j. If the prefix to j is already reachable (dp[j]) and the slice s[j..i) is a dictionary word, mark dp[i] = true. The breakis a small optimization — once we find one valid split, there's no need to check others.dp[n]asks exactly “can the whole string be segmented?” — the original question, answered by building up from smaller sub-answers.dp[i] = true position to reconstruct the actual word sequences — watch for exponential output size.s forward from each reachable index without hashing every substring — reduces repeated prefix work.canBreak(i) (can s[i..n) be segmented?) is equivalent and some find it easier to derive.| "can string be segmented into words" | boolean DP + hash set |
| partition / split string into valid pieces | dp[i] = OR over j < i of dp[j] && word(j,i) |
| reuse allowed, reconstruct sentences | Word Break II: memoized DFS |
| similar: decode ways, palindrome min-cuts | same reachable-prefix DP shape |
function wordBreak(s: string, wordDict: string[]): boolean {
const dict = new Set(wordDict);
const n = s.length;
const dp = new Array(n + 1).fill(false);
dp[0] = true; // seed: empty prefix
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && dict.has(s.slice(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}dp[i] mean in Word Break?dp[i] = true iff s[0..i) (the first i chars) can be fully segmented into dictionary words.n, dictionary lookup O(1))?dp[0] = true essential?s = "leetcode", wordDict = ["leet", "code"]. What is dp[4]?s = "applepenapple", wordDict = ["apple", "pen"]. What does the algorithm return?dp array have, and what do the indices represent?