You are given a string s with no spaces, and a list of allowed words wordDict.
Check if you can cut s into pieces, one after the other, so that every piece is a word from wordDict.
You may use the same word from wordDict as many times as you want.
Return true if s can be cut this way. Otherwise return false.
Examples
Example 1:
Input: s = "flowerbed", wordDict = ["flower","bed","flow"]
Output: true
Explanation: "flowerbed" can be cut as "flower" + "bed".
Example 2:
Input: s = "chaiandtea", wordDict = ["chai","tea"]
Output: false
Explanation: After "chai", the piece "and" is not in the list.
Example 3:
Input: s = "ababab", wordDict = ["ab"]
Output: true
Explanation: The word "ab" is used three times.