#139
Word Break
Medium Prefix DP
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether a string can be split into a sequence of words from a dictionary (words can be reused).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: can the string be split into dictionary words?
Why this works: ok[i] = the first i letters can be split. ok[i] is true if some ok[j] is true and s[j..i) is a word.
Example: "leetcode", ["leet", "code"]
ok[4] (leet) ✓ → ok[8] (code) ✓ → true✦Hints open one at a time
ok[i] = the first i characters can be split.
ok[i] is true if some j < i has ok[j] and s[j..i) is a dictionary word.
↗Approach
Put the words in a HashSet. ok[0] = true. For each i, try j from i − 1 down to max(0, i − longestWord), stopping on the first success.
</>Solution (Java)
import java.util.*;
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
int maxLen = 0;
for (String w : wordDict) maxLen = Math.max(maxLen, w.length());
boolean[] ok = new boolean[s.length() + 1];
ok[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = i - 1; j >= Math.max(0, i - maxLen); j--) {
if (ok[j] && dict.contains(s.substring(j, i))) { // prefix ok + one more word
ok[i] = true;
break;
}
}
}
return ok[s.length()];
}
}!Common mistake
Greedy matching of the longest word first — it can block a valid split.
Complexity
- Time: O(n · L) substring checks, L = longest word.
- Space: O(n).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon