Decide whether s can be cut into consecutive pieces so that every piece is a word from wordDict. A word may be used more than once, and the pieces must cover all of s. Return true if such a cut exists, otherwise false.
Example 1
Input
s = "sunsetsun", wordDict = ["sun", "set"]
Output
true
Explanation
sun set sun covers the whole string. It uses the word sun twice, which is allowed.
Example 2
Input
s = "bookkeeper", wordDict = ["book", "keep", "per"]
Output
false
Explanation
book keep covers bookkeep and leaves er. per cannot help, because the bookkee in front of it has no valid cut.
Constraints:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
Tab indents. Press Esc, then Tab to leave the editor.
Ctrl or ⌘ + Enter runs the tests.
Run your code to see every test here. Nothing is submitted or recorded.