You get a string s and a list of words, wordDict. Decide whether s can be cut into pieces so that every piece is a word from wordDict. The pieces must cover s exactly, in order, with nothing left over.
A word may be used as many times as you like, or not at all. Return true if such a cut exists, otherwise false.
red | blue | red: the word red is used twice.
sand | wich | es works, and so does san | dwich | es. One way is enough.
Starting with note leaves book; starting with not and then ebo leaves ok. Neither leftover can be cut into words.
Constraints
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s and every wordDict[i] are made of lowercase English letters only.wordDict are all different.Trying every cut with plain recursion repeats the same work: whether the rest of s from position j can be cut doesn't depend on how you reached j. Remember that answer for each position.
Read s from the left and cut off a first piece that's a word. Whatever is left has to be cut the same way. So the question "can s be cut?" turns into "can the rest, from position start, be cut?", for whatever start the first piece leaves you at.
Time O(n · L² + D)Space O(n + D)
The full walkthrough and code are part of Premium
true