Word Break
You are given a string s and a list of words wordDict. Decide whether s can be cut into one or more pieces so that every piece is a word from wordDict.
Words may be used any number of times, and not every word has to be used. The pieces must cover the whole string, in order, with nothing left over. Return true if such a split exists and false otherwise.
Example 1
Example 2
Example 3
Constraints
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20- s and every word consist of lowercase English letters; all words are distinct.
Pattern Path · Dynamic Programming · problem 149 of 169
s.ok[i] mean “the first i characters can be split”. Then ok[0] is true (the empty prefix).ok[i] is true if some j < i has ok[j] true and s[j:i] is a dictionary word. Put the words in a set and only try lengths up to the longest word.Start simple
Recursively try every dictionary word as the next piece and backtrack on failure: exponential time on inputs like "aaaa…ab" with words "a", "aa", "aaa".
The key idea
The plain recursion is slow because it asks the same question again and again: “can the rest of the string, starting at position j, be split?” There are only n + 1 such positions, so remember the answer for each.
Bottom-up, let ok[i] be true when the prefix s[0:i] can be split. The empty prefix trivially can, so ok[0] = true. For a longer prefix, look at its last piece s[j:i]: the prefix splits exactly when that piece is a word and the part before it, s[0:j], splits too. So
ok[i] = any(ok[j] and s[j:i] in words).
The answer is ok[n]. Storing the dictionary in a set makes each lookup fast, and since no word is longer than L characters, only j ≥ i − L needs to be tried. That gives O(n · L) checks, each costing O(L) to slice and hash.
Complexity
- Time:
O(n · L²), L = longest word - Space:
O(n + total dictionary size)
Python
class Solution:
def wordBreak(self, s, wordDict):
words = set(wordDict)
longest = max(map(len, words))
n = len(s)
ok = [False] * (n + 1) # ok[i]: can s[:i] be split into words?
ok[0] = True
for i in range(1, n + 1):
for j in range(max(0, i - longest), i):
if ok[j] and s[j:i] in words:
ok[i] = True
break
return ok[n]JavaScript
var wordBreak = function(s, wordDict) {
const words = new Set(wordDict);
const longest = Math.max(...wordDict.map(w => w.length));
const n = s.length;
const ok = new Array(n + 1).fill(false); // ok[i]: can s[0..i) be split into words?
ok[0] = true;
for (let i = 1; i <= n; i++) {
for (let j = Math.max(0, i - longest); j < i; j++) {
if (ok[j] && words.has(s.slice(j, i))) {
ok[i] = true;
break;
}
}
}
return ok[n];
};What the interviewer is checking
The interviewer wants to see you notice overlapping subproblems in a recursive search and turn them into a prefix DP (or memoised recursion), then tighten the inner loop.
Mistakes to avoid
- Greedy matching (always taking the longest or shortest word), which fails on cases like "cats"/"cat".
- Recursion without memoisation, which is exponential on strings of repeated letters.
- Searching a list instead of a set for each piece, making every lookup O(dictionary size).
Follow-ups to expect
- Return every possible sentence. (Memoised DFS returning lists.)
- What if the dictionary is huge? (Trie walk from each start index.)
- Find the split with the fewest pieces. (Min instead of boolean OR.)
In real software
Segmenting text without spaces (URLs, hashtags, languages written without word gaps) and tokenisers that split words into known sub-word units solve this same prefix DP.