Problem overview
The method wordBreak receives a string s and an array of strings wordDict. It returns true when s can be cut into one or more dictionary words, laid one after another with no characters left over, and false otherwise. A word may be used as many times as you like.
With s = "leetcode" and wordDict = ["leet", "code"] the answer is true: "leet" followed by "code". With "applepenapple" and ["apple", "pen"] it is also true, using "apple" twice. With "catsandog" and ["cats", "dog", "sand", "and", "cat"] it is false: both "cat" + "sand" and "cats" + "and" leave "og", which is not a word.
The statement 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: which prefixes can be split?
The direct idea is to try every way of cutting the string. That is hopeless in the worst case: with s made of many as followed by a b, and the words "a", "aa", "aaa" and so on, the number of ways to cut the as grows exponentially, and none of them works.
The fix is to solve smaller versions of the same question and reuse the answers. Let dp[i] say whether the first i characters of s can be split into words. Two facts define the table:
dp[0]istrue. The empty prefix needs no words, and every split has to start from it.dp[i]istruewhen some dictionary wordwends exactly at positioniand the part before that word,dp[i - w.length], is alreadytrue.
Each entry depends only on shorter prefixes, so filling the table from left to right always has the needed answers ready. The answer to the whole problem is dp[n].
For "leetcode" with ["leet", "code"] the table ends up as follows (position: splittable):
0:T 1:F 2:F 3:F 4:T 5:F 6:F 7:F 8:T
Position 4 is true because "leet" ends there and dp[0] is true. Position 8 is true because "code" ends there and dp[4] is true. For "catsandog" with the five words, the table is:
0:T 1:F 2:F 3:T 4:T 5:F 6:F 7:T 8:F 9:F
Positions 3 ("cat"), 4 ("cats") and 7 ("sand" after "cat", or "and" after "cats") are reachable. Nothing ends at 9, because "og" is not a word, so dp[9] stays false.
Step by step
- Store the length of
sinn. The table has an entry for every prefix length from 0 ton, so this number is used again and again. - Create
dpwithn + 1entries, allfalse. A prefix counts as splittable only once a split has been found for it. - Set
dp[0]totrue. The first word of any split follows the empty prefix. - Loop
ifrom 1 toninclusive. Entrynis the whole string, so the loop must reach it. - Try every word with a
for...ofloop: each one is a candidate for the last word of a split of the firsticharacters. - Compute
start, the index where the word would begin if it ended the prefix:i - word.length. It is negative when the word is longer than the prefix. - Check three conditions with
&&: the word fits (start >= 0), the part before it can be split (dp[start]), and the characters fromstartup toireally spell the word. The checks run left to right and stop at the first one that fails, so the text is compared only when the earlier checks pass. - Set
dp[i]totrue. One word that works is enough. - Return
dp[n]after the outer loop.
The solution in TypeScript
class Solution {
wordBreak(s: string, wordDict: string[]): boolean {
const n = s.length;
const dp: boolean[] = 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];
}
}
Some TypeScript details worth knowing:
new Array(n + 1).fill(false)createsn + 1empty slots and fills every one withfalse. Withoutfill, the slots would be empty and read asundefined. The annotationboolean[]is only for the compiler; it is erased when the code becomes JavaScript.substring(start, i)returns the characters from indexstartup to, but not including, indexi. That is exactly the lastword.lengthcharacters of the prefix. Unlikeslice,substringtreats a negative argument as 0:"abc".substring(-1, 2)is"ab". That is another reason to teststart >= 0first rather than rely on the other checks.- Reading outside an array does not throw in TypeScript or JavaScript.
dp[-2]isundefined, which is falsy, so a missingstart >= 0check would not crash. It is still the clearer way to say "the word fits". ===on strings compares the characters, sos.substring(start, i) === wordis a real text comparison.for (const word of wordDict)gives each element directly.for...inwould give indices as strings, which is not what you want here.
Complexity
Time: O(n · m · k). The table has n + 1 entries. For each one the inner loop tries m words, and comparing a word with the end of the prefix takes up to k character comparisons.
Space: O(n). The table holds one boolean per prefix length. The substring built for each comparison is at most k characters long.
When the dictionary is large, a variant puts the words in a Set and, for each i, looks up only the pieces of length 1 up to k that end at i. It returns the same answers on the examples above, and it does not depend on m.
Edge cases and common mistakes
- No word fits.
"a"with["b"]returnsfalse, becausedp[1]is never set. - A word longer than the string.
"aaaa"with["aaaaa"]returnsfalse: for everyi,startis negative. - Almost splittable.
"aaaaaaab"with["a", "aa", "aaa"]returnsfalse. The first seven characters are all splittable, but nothing ends withb. - Several words share a start.
"abcd"with["abcd", "abc"]returnstrue. Only the word that ends exactly at the end of the string counts fordp[4];"abc"setsdp[3]and leaves a"d"that is not a word. - Forgetting
dp[0] = true. Then no entry ever becomes true, since every split starts from the empty prefix. - Looping to
i < n. The table is then never filled at indexn, sodp[n]stays false. - Checking only the text. Testing that a word ends at
iwithout checkingdp[start]accepts splits that leave a bad piece in front. In"catsandog","dog"does end at 9, butdp[6]is false.
Testing
"leetcode",["leet", "code"]givestrue."applepenapple",["apple", "pen"]givestrue."catsandog",["cats", "dog", "sand", "and", "cat"]givesfalse."a",["b"]givesfalse."aaaaaaab",["a", "aa", "aaa"]givesfalse."abcd",["abcd", "abc"]givestrue."aaaa",["aaaaa"]givesfalse.
