wordDict
s the bracket is the substring s.substring(i, i + w.length()) being compared with w
dp dp[i] = true if s.substring(i) breaks into words · dp[n] = true (the empty tail)
public boolean wordBreak(String s, List<String> wordDict) { boolean[] dp = new boolean[s.length() + 1]; dp[s.length()] = true; for (int i = s.length() - 1; i >= 0; i--) { for (String w : wordDict) { if (i + w.length() <= s.length() && s.substring(i, i + w.length()).equals(w)) { dp[i] = dp[i + w.length()]; } if (dp[i]) { break; } } } return dp[0];}
- i
- —
- w
- —
- substring
- —
- dp[i]
- —
Why it works
- Brute force tries every first word, then recurses on the rest: without memory the same suffix is solved again and again, exponential on inputs like
"aaaaaaab". - Suffixes are the subproblems:
s.substring(i)breaks into words exactly when some wordwmatches atiand the suffix after it,s.substring(i + w.length()), breaks too. That isdp[i] = dp[i + w.length()]for a matchingw; the arcs show that hop. - Right to left, one cell each: every arc points from a cell further right, already final. n positions × m words × an O(L) substring compare: O(n · m · L) time, O(n) space. (
s.startsWith(w, i)does the same compare without copying the substring.) - Pitfall: taking the first match greedily. In
"cars"with["car","ca","rs"],"car"matches at 0 but leaves"s". The dp tries every word and only stops when one leads to a true cell. - Break early: once
dp[i]is true no other word can change it, so the loop moves on. - Related: Word Break II lists every sentence (backtracking with memo). A trie over the words speeds up the matching when the dictionary is large.