Problem overview
The method wordBreak receives a string s and a list of words wordDict. It returns True when s can be cut into one or more dictionary words laid end to end with nothing left over, and False otherwise. A word can be used as many times as needed.
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, and "apple" is used 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 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: solve every prefix once
The direct idea is to try every way of cutting the string. That is hopeless in the worst case. With s made of many "a" characters followed by a "b", and the words "a", "aa", "aaa" and so on, the number of ways to cut the a's grows exponentially, and none of them works because of the final "b".
The way out is to notice that the same smaller questions come up again and again. Let dp[i] be True when the first i characters of s can be split into words. Then:
dp[0]isTrue. The empty prefix needs no words.dp[i]isTruewhen some wordwends the prefix, and the part beforewcan itself be split. In symbols: the word fits,s[i - len(w):i] == w, anddp[i - len(w)]isTrue.- The answer is
dp[n], the whole string.
Each entry depends only on entries to its left, so filling the table from left to right works. This is dynamic programming: each prefix is solved once, from the answers for shorter prefixes.
For "leetcode" with ["leet", "code"] the finished table, indexed from 0 to 8, is:
[True, False, False, False, True, False, False, False, True]
Position 4 is True because "leet" ends there and position 0 is True. Position 8 is True because "code" ends there and position 4 is True. For "catsandog" with ["cats", "dog", "sand", "and", "cat"] the table is:
[True, False, False, True, True, False, False, True, False, False]
Positions 3, 4 and 7 are reachable ("cat", "cats" and the "and" or "sand" that follow), but the last entry stays False.
Step by step
- Store the length of
sinn. It is needed for the table and for the loop. - Create the table
dpwithn + 1entries, allFalse. There is one entry for every prefix length from 0 ton, and a prefix counts as splittable only once a split is found. - Set
dp[0]toTrue. Every split starts from the empty prefix. - Loop over
iinrange(1, n + 1).rangestops before its end, so the last value isn, the whole string. - Loop over the words. Each one is tried as the last word of a split of the first
icharacters. - Compute
start,i - len(word): where the word would begin if it ended the prefix. It is negative when the word is longer than the prefix. - Check three things with
and: the word fits (start >= 0), the part before it can be split (dp[start]), and the prefix really ends with the word (s[start:i] == word). - Mark
dp[i]asTrueinside theif. One word that works is enough. - Return
dp[n]after both loops.
The solution in Python
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for word in wordDict:
start = i - len(word)
if start >= 0 and dp[start] and s[start:i] == word:
dp[i] = True
return dp[n]
Python details worth a closer look:
- The order of the checks matters.
andstops at the first check that is false. Ifstartis negative,dp[start]is never read. That matters because Python accepts negative list indexes: withdp = [True, False],dp[-1]isFalse, the last element, and no error is raised. Without the guard, a long word would quietly read the wrong entry. Puttingdp[start]before the string comparison also skips the comparison whenever the prefix before the word can't be split. - Slices are forgiving, indexes are not.
s[start:i]holds the characters from indexstartup toi - 1, so it has exactlylen(word)characters whenstart >= 0. [False] * (n + 1)creates a list ofn + 1separate booleans. Repeating an immutable value like this is safe. (Repeating a list inside a list, as in[[]] * 3, would share one inner list.)- The loop keeps going after
dp[i]is set. The solution doesn'tbreak; setting an entry toTrueagain changes nothing. Addingbreakafter the assignment is a valid small speed-up.
Complexity
Time: O(n · m · k). The outer loop runs n times, the inner loop runs m times for each, and comparing a word with the end of the prefix takes up to k character comparisons.
Space: O(n). The table has n + 1 entries. The slice s[start:i] is a temporary string of at most k characters.
When the dictionary is large, a variation puts the words in a set and, for each i, looks up only the pieces of length 1 to k that end at i. That replaces the loop over m words with a loop over at most k lengths.
Edge cases and common mistakes
- Forgetting
dp[0] = True. Then no entry can ever becomeTrue, because every first word of a split relies on it. The function always returnsFalse. - Dropping the
start >= 0check. Negative indexes read from the end of the list instead of failing, which produces wrong answers silently. - Checking only that the word appears in
s. The word has to end exactly at positioni, and the part before it has to be splittable."ba"with["ab"]contains"ab"but isn't splittable; the function returnsFalse. - Greedy matching. Taking the first word that fits can fail where another split works. The table tries every word at every position, so
"aaaa"with["a", "aa"]works regardless of order. - Returning
dp[n - 1]. Indexnstands for the firstncharacters, which is the whole string.
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 = "ab",wordDict = ["a", "b"]givesTrue.s = "ba",wordDict = ["ab"]givesFalse.s = "aaaa",wordDict = ["a", "aa"]givesTrue.
