Word Break
Given a string and a dictionary of words, decide whether the string can be split into a sequence of dictionary words. Words may be reused.
- 1 ≤ s.length ≤ 300
- 1 ≤ wordDict.length ≤ 1000
- 1 ≤ word length ≤ 20
- Lowercase letters
- Is prefix
s[0..i)segmentable? — a boolean over prefixes - A prefix is good if some earlier good prefix plus one dictionary word reaches it
- Overlapping subproblems if done naively
Counting or optimizing over choices where a brute-force recursion revisits the same state signals DP: define the state so the answer to a state depends only on smaller states, then memoize or fill a table bottom-up. Subsequence (not subarray) wording, "number of ways", and "minimum/maximum over all choices" are the classic tells.
Let ok[i] mean the first i characters can be segmented, with ok[0] = true. For each i, look back at each j < i (bounded by the maximum word length) and set ok[i] if ok[j] and s[j..i) is in the dictionary set. Return ok[n]. Bounding the look-back by the longest word keeps the inner loop short.
- Memoized DFS from each start index is the same DP top-down. A trie over the dictionary avoids building substrings during the inner loop.