Problem overview
The function wordBreak gets a string s and a slice of strings 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 may be used as many times as needed.
With s = "leetcode" and wordDict = ["leet", "code"] the answer is true: "leet" followed by "code". With s = "applepenapple" and the words "apple" and "pen" it is also true, and "apple" is used twice. With s = "catsandog" and the words "cats", "dog", "sand", "and" and "cat" it is false: both "cat" + "sand" and "cats" + "and" leave "og", which is no 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: solve every prefix once
The direct idea is to try every way to cut the string. That is hopeless: for s made of many as followed by a b, with the words "a", "aa", "aaa" and so on, the number of ways to cut the as grows exponentially, and none of them works because of the final b.
The way out is to notice that the same questions repeat. 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, and every split starts from it.dp[i]istruewhen some wordwends the prefix and the part in front of it can be split. IfwhasLcharacters, that meansL <= i, the characters from positioni - Lup toispellw, anddp[i - L]istrue.
The answer is dp[n]. Each entry only looks at shorter prefixes, which are already done when the loop reaches it, so one pass from left to right is enough.
Step by step
- Store the length.
n := len(s)is used for the table size, the loop bound and the final answer. - Create the table.
make([]bool, n+1)has one entry per prefix length from 0 ton. A new slice of bools is filled withfalse, which is the right start: a prefix counts only once a split is found. - Set
dp[0] = true. This is the base case the first word of every split builds on. - Loop over prefix lengths from 1 to
ninclusive. The bound isi <= nbecausedp[n]is the entry we want. - Try each word as the last word of the prefix, with
for _, word := range wordDict. The index is not needed, so_discards it. - Compute where the word would start:
start := i - len(word). The prefix ends at indexi - 1, so a word oflen(word)characters that ends it begins ati - len(word). That value is negative when the word is longer than the prefix. - Check three things in one
if, joined by&&: 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 the entry. One word that works is enough, so
dp[i] = true. - Return
dp[n]after the loop.
The solution in Go
func wordBreak(s string, wordDict []string) bool {
n := len(s)
dp := make([]bool, n+1)
dp[0] = true
for i := 1; i <= n; i++ {
for _, word := range wordDict {
start := i - len(word)
if start >= 0 && dp[start] && s[start:i] == word {
dp[i] = true
}
}
}
return dp[n]
}
The Go details worth a closer look:
- The order of the checks matters.
&&stops at the firstfalse. Becausestart >= 0comes first,dp[start]is never read with a negative index. Without that check,wordBreak("leetcode", []string{"leet", "code"})stops with the panicruntime error: index out of range [-3], since ati = 1the word"leet"givesstart = -3. Puttingdp[start]before the comparison also means the text is compared only when the front part already splits. s[start:i]is a substring. Slicing a string takes the bytes fromstartup to, but not including,i. It does not copy them.==compares two strings by their contents.- Bytes and letters.
len(word)counts bytes. The lesson's strings hold only lowercase lettersatoz, one byte each, so bytes and letters are the same thing here. make([]bool, n+1)givesn+1entries, allfalse. Indexingdp[n]is valid because the last index isn.
Complexity
Time: O(n · m · k). The table has n + 1 entries. For each one the code tries 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.
When the dictionary is large, you can keep the words in a map[string]bool and, for each i, look up only the pieces of length 1 to k that end at i. That replaces the loop over m words by at most k lookups.
Edge cases and common mistakes
- Leaving out
dp[0] = true. Then no entry can ever becometrue, and the function always returnsfalse. - Checking only the start of the string. A greedy rule such as "take the first word that matches" fails: for
s = "cars"and the words"car","ca"and"rs", taking"car"leaves"s", yet"ca" + "rs"works. The function returnstruebecausedp[4]is reached throughdp[2]. - A prefix that works but leaves a tail. For
s = "catsandog",dp[7]istrue, butdp[9]is not, because nothing ends at the finalgfrom a splittable position. Onlydp[n]answers the question. - A word longer than the string.
wordBreak("a", []string{"b"})returnsfalse, and a longer word such as"abc"is skipped through thestart >= 0check.
Testing
Here is the table for s = "leetcode" with ["leet", "code"], entries dp[0] to dp[8]:
[true false false false true false false false true]dp[4] is true because "leet" ends the prefix and dp[0] is true. dp[8] is true because "code" ends the string and dp[4] is true. For "catsandog" the table is:
[true false false true true false false true false false]The last entry is false, so the answer is false. More inputs to try:
s = "applepenapple", words["apple", "pen"]givestrue.s = "abcd", words["a", "abc", "b", "cd"]givestrue("a" + "b" + "cd").s = "cars", words["car", "ca", "rs"]givestrue.s = "a", words["b"]givesfalse.smade of 29as followed byb, words["a", "aa", "aaa", "aaaa"]givesfalse, quickly.
