Word Break
Can a string be segmented into dictionary words? 1D DP with O(n²) substring checks (or trie).
dpstringshashset
Intro
Given a string and a dictionary, decide if the string can be split into a sequence of dictionary words.
Key insight
dp[i] = true if some j < i has dp[j] and s[j..i-1] is in the dictionary.
Approach
- 1Put dictionary words in a set.
- 2dp[0] = true (empty prefix).
- 3For each i in 1..n, scan j in 0..i-1; if dp[j] and s[j..i-1] in set, set dp[i] true.
Complexity
Time
O(n² · m) where m is the average substring check (hash) cost
Space
O(n)
Code
Snippetjava
boolean wordBreak(String s, List<String> dict) {
Set<String> set = new HashSet<>(dict);
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && set.contains(s.substring(j, i))) { dp[i] = true; break; }
}
}
return dp[n];
}Pitfalls
- Considering substrings longer than the longest word in the dictionary — wasteful.
- Recursing without memoisation — exponential.
Variants & follow-ups
- Word Break II (LC 140) — return all decompositions