You are given a string s and a list of words wordDict. Return true if s can be cut into
pieces so that every piece is a word in wordDict, and false otherwise.
You may use a word as many times as you like, and you don't have to use every word.
Example 1
- Input
- s = "sunflowerpot", wordDict = ["flower", "sun", "pot", "flowerpot"]
- Output
- true
sun + flower + pot works, and so does sun + flowerpot.Example 2
- Input
- s = "carpet", wordDict = ["car", "carp", "pe"]
- Output
- false
car or carp, what is left (pet or et) can't be made from the words.Example 3
- Input
- s = "aaaaaaa", wordDict = ["aaa", "aaaa"]
- Output
- true
aaa + aaaa.Constraints
sholds 1 to 300 lowercase letters.wordDictholds 1 to 1000 different words, each of 1 to 20 lowercase letters.
Show the pattern
Dynamic programming (1D)
Whether the first i characters split into words depends only on whether some shorter prefix does and the piece after it is a word: one yes-or-no answer per position, built from left to right.
See dynamic programming (1d) in a visualiserShow the approach
Let ok[i] be true when the first i characters of s can be cut into words. The empty prefix
needs no words, so ok[0] is true. A longer prefix of length end splits when its last piece,
s[start:end], is a word and the prefix before that piece, of length start, splits too.
Fill ok from left to right, trying each start that leaves a last piece no longer than the
longest word, and looking the piece up in a set of the words. The answer is ok[len(s)].
Plain recursion without the table tries the same suffixes over and over: a string of many as
ending in b makes it take exponential time.
Time: O(n × L²) for a longest word of length L (n × L pieces, each up to L long) · Space: O(n) plus the set of words