Problem overview
The function word_break receives a string s and a vector of words, word_dict. It returns true when s can be cut into pieces that are all dictionary words, laid one after another with nothing left over. A word may be used as many times as you like.
With s = "leetcode" and the words ["leet", "code"] the answer is true: the string is "leet" followed by "code". With s = "applepenapple" and ["apple", "pen"] it is also true, because "apple" is used twice. With s = "catsandog" and ["cats", "dog", "sand", "and", "cat"] it is false: both "cat" + "sand" and "cats" + "and" leave "og", which is not a 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: can each prefix be split?
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, and none of them works because of the final b.
The fix is to solve smaller versions of the problem. Let dp[i] be true when the first i characters of s can be split into words. The answer is dp[n], the whole string.
How is dp[i] decided? If the first i characters can be split, the split has a last word. Call it word, with L characters. Then two things hold: the last L characters of the prefix spell word, and the part before them, the first i - L characters, can be split too. That second fact is already in the table, because i - L is smaller than i. So each entry is built from earlier ones, which is what makes this dynamic programming.
The base case is dp[0] = true: the empty prefix needs no words. Every split starts from it.
For "leetcode" with ["leet", "code"] the finished table, from dp[0] to dp[8], is:
[true, false, false, false, true, false, false, false, true]
Entry 4 is true because "leet" ends there and dp[0] is true. Entry 8 is true because "code" ends there and dp[4] is true. For "catsandog" the table is:
[true, false, false, true, true, false, false, true, false, false]
"cat" ends at 3, "cats" at 4, and "sand" and "and" both end at 7, but nothing ends at 9, so the last entry is false.
Step by step
- Store the length.
n = s.len()is used for the table size and the loop bound. The string holds only the letters a to z, one byte each, so its length in bytes is its number of characters. - Create the table.
vec![false; n + 1]has one entry for every prefix length from 0 ton. A prefix counts as splittable only once a split is found, so everything starts as false. - Set
dp[0]to true, the empty prefix. - Loop over prefix lengths from 1 to
ninclusive. The range1..=nincludesn, and every entry depends only on shorter prefixes, which are finished by then. - Try each word as the last word of the current prefix, borrowing the vector with
&word_dictso nothing is copied. - Check three things, joined by
&&: the word fits in the prefix, the part before it can be split, and the slice that ends the prefix equals the word. - Mark
dp[i]true when all three hold. One word that works is enough. - Return
dp[n]without a semicolon, as the function's final expression.
The solution in Rust
impl Solution {
fn word_break(s: String, word_dict: Vec<String>) -> bool {
let n = s.len();
let mut dp = vec![false; n + 1];
dp[0] = true;
for i in 1..=n {
for word in &word_dict {
if word.len() <= i && dp[i - word.len()] && &s[i - word.len()..i] == word {
dp[i] = true;
}
}
}
dp[n]
}
}
The Rust details worth a closer look:
- The order of the three checks matters. Indexes are
usize, which can't go below zero. Ifword.len()is 4 andiis 2, the subtractioni - word.len()underflows: it panics in a debug build and wraps to a huge number in an optimized build, and the indexing that follows would then panic. Because&&stops at the first check that fails,word.len() <= iruns first and the subtraction only happens when it is safe. - Slicing a string.
&s[a..b]is a&strholding the bytes fromaup to, but not including,b. Slicing aStringuses byte positions, not character positions. That works here because the letters are all one byte each. With text that has multi-byte characters, a cut in the middle of a character panics. - Comparing the slice with
word.wordis a&String, because the loop borrows the vector. The left side is a&str, and Rust can compare a&strwith a&Stringby their text, so the comparison checks the characters, not addresses. for word in &word_dict. Looping over the vector itself would move it into the loop, and it would be unusable for the next value ofi. The&borrows it each time.- Final expression.
dp[n]has no semicolon, so it is the value the function returns. AboolisCopy, so reading it out of the vector is fine.
Complexity
Time: O(n · m · k). The table has n + 1 entries. Each one tries the m words, and comparing a word with the end of the prefix takes up to k character comparisons, where k is the length of the longest word.
Space: O(n). The only extra memory is the table of n + 1 booleans. When the dictionary is large, an alternative is to put the words in a HashSet and, for each i, look up only the pieces of length 1 to k that end at i.
Edge cases and common mistakes
- A word longer than the prefix. Skipping the length check turns
i - word.len()into an underflow. Withs = "a"and the word"b"nothing breaks, but any longer word in the dictionary would. - Greedy matching. Taking the longest word that fits at each point can fail. With
s = "cars"and the words["car", "ca", "rs"], grabbing "car" leaves "s", which is not a word, yet "ca" + "rs" works. The table finds it, because every prefix is judged independently. - Leftover characters. The words must cover the whole string. For
s = "aaaaaaab"with["a", "aa", "aaa"]the first seven characters can be split in many ways, but the answer isfalse, because no word ends at position 8. - Returning the wrong entry. The answer is
dp[n], notdp[n - 1]: the table hasn + 1entries because it includes the empty prefix. - A word used more than once. Nothing in the loop marks a word as used, so repeated words work without extra code, as in "applepenapple".
Testing
s = "leetcode", words["leet", "code"]givestrue.s = "applepenapple", words["apple", "pen"]givestrue.s = "catsandog", words["cats", "dog", "sand", "and", "cat"]givesfalse.s = "a", words["b"]givesfalse.s = "aaaaaaab", words["a", "aa", "aaa"]givesfalse.s = "abcd", words["abcd", "abc"]givestrue.s = "cars", words["car", "ca", "rs"]givestrue.
