Problem overview
The method wordBreak(s, wordDict) receives a string s and an array of words. It returns true when s can be cut into pieces that are all dictionary words, with nothing left over, and false otherwise. A word can be used as many times as you like.
For s = "leetcode" and wordDict = ["leet", "code"] the answer is true: the string is "leet" followed by "code". For "applepenapple" with ["apple", "pen"] it is also true, using "apple" twice. For "catsandog" with ["cats", "dog", "sand", "and", "cat"] it is false: both "cat" + "sand" and "cats" + "and" leave "og", which is not a word.
The lesson asks for O(n · m · k) time and O(n) extra space, where n is the length of s, m the number of words and k the length of the longest word.
Approach: answer the question for every prefix
Trying every way to cut the string is far too slow. With s = "aaa…ab" and the words "a", "aa", "aaa", the a's can be cut in exponentially many ways, and none of them works because of the final b. A search that explores each way separately repeats the same work again and again.
Dynamic programming avoids that by solving smaller versions of the problem first. Let dp[i] be true when the first i characters of s can be split into words. Two facts define the whole table:
dp[0]istrue. The empty prefix needs no words, and every split has to start from it.dp[i]istruewhen some wordwends the prefix and the part beforewcan be split. IfwhasLcharacters, that means the prefix is at least that long, its lastLcharacters spellw, anddp[i - L]istrue.
The answer is dp[n], the entry for the whole string. For "leetcode" the table, read from index 0 to 8, comes out as:
0:true 1:false 2:false 3:false 4:true 5:false 6:false 7:false 8:trueIndex 4 is true because "leet" ends there and dp[0] is true. Index 8 is true because "code" ends there and dp[4] is true.
Step by step
- Store the length.
n = s.lengthis used for the table size, the loop bound and the final answer. - Create the table.
new Array(n + 1).fill(false)has one entry for each prefix length from 0 ton. Everything starts asfalse: a prefix counts only once a split has been found for it. - Set
dp[0]totrue. This is the base case that every othertruegrows from. - Loop over prefix lengths from 1 up to and including
n. Each entry needs only shorter prefixes, which are already filled in by the time the loop reaches it. - Try each word as the last word of the prefix with a
for...ofloop overwordDict. - Compute where the word would start. A prefix of
icharacters ends at indexi - 1, so a word ofword.lengthcharacters ends it by starting ati - word.length. That number is negative when the word is longer than the prefix. - Check three things together. The word fits (
start >= 0), the part before it can be split (dp[start]), and the prefix really ends with the word (s.substring(start, i) === word). The checks run left to right and stop at the first one that fails, so the text comparison happens only when the cheaper checks passed. - Mark the entry. One word that works is enough, so
dp[i] = true. - Return
dp[n].
The solution in JavaScript
class Solution {
wordBreak(s, wordDict) {
const n = s.length;
const dp = new Array(n + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= n; i++) {
for (const word of wordDict) {
const start = i - word.length;
if (start >= 0 && dp[start] && s.substring(start, i) === word) {
dp[i] = true;
}
}
}
return dp[n];
}
}
A few JavaScript details matter here:
substring(start, i)excludesi. It returns the characters from indexstartup toi - 1, which is exactlyword.lengthcharacters.- The
start >= 0check is not optional.substringtreats a negative index as 0 instead of failing:"abc".substring(-1, 2)is"ab". Without the check, a word longer than the prefix would be compared against a piece that starts at the wrong place. - Use
===for the comparison. Strings are compared by their characters, sos.substring(start, i) === wordistruewhen the text matches, even though the two strings are different objects in memory. fill(false)is safe here. The entries are booleans, which are copied by value. Filling an array of arrays this way would not be safe, because every row would be the same array.for...ofover an array gives the words themselves, not their indexes, which is why the loop variable is namedword.
Complexity
Time: O(n · m · k). The table has n + 1 entries. Each one tries all m words, and comparing a word with the end of the prefix takes up to k character comparisons.
Space: O(n). The table is the only structure that grows with the input. The pieces cut by substring are short and temporary.
When the dictionary is large, you can put the words in a Set and, for each i, look up only the pieces of length 1 to k that end at i. That replaces the loop over all m words with at most k lookups.
Edge cases and common mistakes
- Forgetting
dp[0] = true. Every entry staysfalse, and every call returnsfalse. - Greedy matching. Taking the first word that matches at the front can fail. For
"abcd"with["ab", "abc", "cd"]the answer istrue("ab" + "cd"), but taking"abc"first leaves"d". The table considers every word at every position. - Reusing words.
"abab"with["ab"]istrue: the table never marks a word as used up. - Returning the wrong entry. The result is
dp[n], not the last entry that happens to betrue. For"ab"with["abc"]no word fits, and the answer isfalse. - Using
i < n. The loop must includei = n, because that entry is the answer.
Testing
s = "leetcode",wordDict = ["leet", "code"]givestrue.s = "applepenapple",wordDict = ["apple", "pen"]givestrue.s = "catsandog",wordDict = ["cats", "dog", "sand", "and", "cat"]givesfalse.s = "a",wordDict = ["b"]givesfalse.s = "aaaaab",wordDict = ["a", "aa", "aaa"]givesfalse.s = "abcd",wordDict = ["ab", "abc", "cd"]givestrue.
