139. Word Break

Practice Word Break for free on NudgeCode: Medium, Dynamic Programming pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Return whether s can be cut into pieces so that every piece is a word from wordDict. A word may be used any number of times.

Example

s = "leetcode", wordDict = ["leet","code"]                        ->  true
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]   ->  false

Constraints

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• All strings are lowercase English letters; words in wordDict are distinct