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, because "apple" is used 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: ask the question for every prefix
Trying every way to cut the string is far too slow. With s = "aaaaaaab" and the words "a", "aa" and "aaa", the number of ways to cut the a's grows exponentially as the string grows, and none of them works, because nothing matches the final b.
The way out is to solve smaller versions of the same problem. Let dp[i] be true when the first i characters of s can be split into words. The empty prefix needs no words, so dp[0] is true, and the answer to the whole problem is dp[n].
To decide dp[i], look at what the last word of the split could be. If a word w with L characters ends the prefix, then the prefix is splittable when the part before that word, the first i - L characters, is splittable: dp[i - L] is true. So for each i you try every word. One word that fits is enough.
The table for "leetcode" with ["leet", "code"], entries dp[0] to dp[8]:
T F F F T F F F Tdp[4] is true because "leet" ends there and dp[0] is true. dp[8] is true because "code" ends there and dp[4] is true. For "catsandog" the table is:
T F F T T F F T F FThe prefixes of lengths 3, 4 and 7 split ("cat", "cats", "catsand"), but the last two entries stay false, so the answer is false.
Step by step
- Copy the characters into an array. A Swift
Stringcan't be indexed with an integer, soArray(s)gives something you can read by position and cut into pieces. - Store the count in
n. The table has one entry per prefix length, so this number comes up often. - Create
dpasn + 1values, allfalse. It is avarbecause the loops write into it. A prefix counts as splittable only after a split is found. - Set
dp[0]totrue. Every split starts from the empty prefix. - Loop
iover1..<n + 1. The range stops beforen + 1, son, the whole string, is the last length. Each entry needs only shorter prefixes, which are already filled in. - Loop over
wordDict. Each word is a candidate for the last word of a split of the firsticharacters. - Compute
startasi - word.count, the index 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
&&: the word fits (start >= 0), the part before it splits (dp[start]), and the prefix really ends with the word (String(chars[start..<i]) == word). - Mark
dp[i]astrueinside theif. - Return
dp[n]after the outer loop.
The solution in Swift
class Solution {
func wordBreak(_ s: String, _ wordDict: [String]) -> Bool {
let chars = Array(s)
let n = chars.count
var dp = [Bool](repeating: false, count: n + 1)
dp[0] = true
for i in 1..<n + 1 {
for word in wordDict {
let start = i - word.count
if start >= 0 && dp[start] && String(chars[start..<i]) == word {
dp[i] = true
}
}
}
return dp[n]
}
}
The Swift details worth a closer look:
- Array of characters.
Array(s)is an[Character], sochars[1]works wheres[1]would not compile.chars.countands.countagree, since both count characters. - Slicing.
chars[start..<i]is anArraySlice<Character>, not a string.String(...)builds a string from it, and==compares the contents of two strings. - Order of the checks.
&&stops at the firstfalse. Whenstartis negative,dp[start]is never read. Swift traps on an out-of-range index and the program crashes, so swapping the first two checks would crash the moment a word is longer than the prefix. The text comparison also runs only when the part before the word is splittable. - Range precedence. In
1..<n + 1, the+is applied first, so the range is1..<(n + 1). It could also be written1...n. Both are fine becausesis never empty here; with an empty stringnis 0 and1...0crashes at run time, since the lower bound is larger than the upper one. - Value types.
dpis an array, which is a value type. Assigningdp[i] = truechanges the array in place becausedpis avar.
Complexity
Time: O(n · m · k). The table has n + 1 entries. Each one 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 n + 1 booleans, and the character array holds n characters. The temporary strings are at most k characters long.
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.
Edge cases and common mistakes
- Leftover characters. A split must use the whole string.
"catsandog"has plenty of matching words but the answer isfalsebecause "og" is left over. - Reusing words.
"applepenapple"needs "apple" twice. The loop never removes a word from consideration, so reuse is automatic. - Words that overlap in meaning.
"abcd"with["abcd", "ab"]istruethrough the single word "abcd", even though "ab" leaves "cd". A greedy approach that always takes the shortest or longest match can fail; the table tries every word at every position. - No word fits.
"a"with["b"]givesfalse:dp[1]is never set. - Reading before checking. Putting
dp[start]beforestart >= 0reads index-1and crashes the program.
Testing
"leetcode",["leet", "code"]givestrue."applepenapple",["apple", "pen"]givestrue."catsandog",["cats", "dog", "sand", "and", "cat"]givesfalse."a",["a"]givestrue."a",["b"]givesfalse."aaaaaaab",["a", "aa", "aaa"]givesfalse."abcd",["abcd", "ab"]givestrue."cars",["car", "ca", "rs"]givestrue.
