Problem overview
The function wordBreak receives a string s and a vector<string> called wordDict. It returns true when s can be cut into one or more dictionary words, written one after another with nothing left over, and false otherwise. A word may be used any number of times.
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, with "apple" 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 and doesn't start with one.
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: can this prefix be split?
Trying every way to cut the string is too slow. With s = "aaaaaaab" and the words "a", "aa" and "aaa", the number of ways to cut the a's grows exponentially, and none of them works, because the final b is never covered.
The way out is to solve smaller versions of the same question. 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].
A prefix of length i can be split exactly when it ends with some dictionary word w and the part in front of that word can be split too. If w has L characters, three things must hold: the word fits (L <= i), the L characters that end the prefix spell w, and dp[i - L] is true. Trying every word for every i covers all the possible last words, and one that works is enough.
For "leetcode" the table, written as one digit per entry from dp[0] to dp[8], comes out as 100010001. Only dp[0], dp[4] and dp[8] are true: "leet" ends at 4, and "code" fits after it and ends at 8. For "catsandog" the table is 1001100100: entries 3 ("cat"), 4 ("cats") and 7 ("catsand") are true, but entry 9 is false, so the answer is false.
Step by step
- Store the length. Put
s.size()in anintnamedn. It comes up in the table size, the loop bound and the answer. - Create the table. A
vector<bool>nameddpof sizen + 1, allfalse: a prefix counts as splittable only after a split is found for it. - Set
dp[0]totrue. Every split builds on the empty prefix, because the first word of a split comes right after it. - Loop over prefix lengths from 1 up to and including
n. Each entry needs only shorter prefixes, which are finished by then. - Loop over the words with
const string& word. Each word is tried as the last word of the prefix, and the reference avoids a copy of every word. - Compute where the word would start if it ended the prefix:
i - (int) word.size(). The result is negative when the word is longer than the prefix. - Check three conditions joined by
&&: the word fits, the part before it can be split, and the characters really spell the word. - Set
dp[i]totruewhen they all hold. - Return
dp[n]after the outer loop.
The solution in C++
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size();
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (const string& word : wordDict) {
int start = i - (int) word.size();
if (start >= 0 && dp[start] && s.substr(start, word.size()) == word) {
dp[i] = true;
}
}
}
return dp[n];
}
};
The C++ details worth a closer look:
- The cast on
word.size().size()returns an unsigned type. Withi = 2and a word of 5 letters,i - word.size()is18446744073709551613, not-3, so astart >= 0test would always pass. Casting tointfirst gives-3, and the test works as intended. - Short-circuit order.
&&stops at the first false operand. That keepsdp[start]from being read with a negative index, and it skips the string comparison unless the part before the word can already be split. substrcopies.s.substr(start, word.size())builds a new string of up tokcharacters, and==compares two strings character by character. That copy and comparison are thekin the time bound. Becausestartis never abovei, which is at mostn, the call can't throw. A start beyond the end of a string throwsstd::out_of_range.vector<bool>. It stores one bit per entry, anddp[i]returns a small proxy object that reads and writes the bit. It works as a plain table of booleans here; just don't take abool&from it.- The vector parameter is a reference.
vector<string>& wordDictavoids copying the whole dictionary.sis taken by value, which is fine at 300 characters at most.
Complexity
Time: O(n · m · k). The table has n + 1 entries. Each one tries m words, and one attempt costs up to k character operations for the substr and the comparison.
Space: O(n). The table holds n + 1 booleans. Each substr temporary has at most k characters, and k is at most 20.
When the dictionary is large, a faster variant puts the words in an unordered_set and, for each i, looks up only the pieces of length 1 to k that end at i. On "leetcode" with {"leet", "code"} that variant also returns true.
Edge cases and common mistakes
- Forgetting
dp[0] = true. Without it no entry can ever become true, and every answer isfalse. - Checking only that the string starts with a word. A greedy cut can fail where another cut works. For
"abcd"with{"ab", "abc", "cd"}the answer istruethrough"ab" + "cd", but taking the longer"abc"first leaves"d". The table tries every word at every position, so it doesn't commit early. - Skipping the fit check. Without
start >= 0a long word produces a negative index intodp, which is undefined behaviour. - Using unsigned arithmetic for
start. As shown above, the subtraction wraps instead of going negative. - Reading the wrong table entry. The part before the word is
dp[start], the prefix of lengthstart, notdp[start - 1]. - Returning inside the loop. The answer concerns the whole string, so it is read from
dp[n]only after every prefix has been filled in.
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 = "aaaaaaab",wordDict = {"a", "aa", "aaa"}givesfalse.s = "abcd",wordDict = {"ab", "abc", "cd"}givestrue.
