Given a string s and a dictionary of words wordDict, return true if the string s can be broken down into a sequence of space-separated words from the list.

Note: A word from the list may be used more than once in the segmentation.

Example 1:

Input: s = "pieforpie", wordDict = ["apple", "pie", "for"]
Output: true
Explanation: "pieforpie" can be split as "pie" + "for" + "pie".
All parts exist in `wordDict`, and reusing "pie" is allowed.

Example 2:

Input: s = "smartdog", wordDict = ["small", "cat", "dog", "smart"]
Output: true
Explanation: "smartdog" can be split as "smart" + "dog".
Both words are present in `wordDict`.

Example 3:

Input: s = "clockwisedirect", wordDict = ["clock", "wise", "directed"]
Output: false
Explanation: "clock" + "wise" matches the beginning, but "direct" is not in `wordDict`.
The available word is "directed", which does not fit the remaining substring exactly.

Example 4:

Input: s = "bedtime", wordDict = ["time", "light", "beds"]
Output: false
Explanation: Although "time" is in `wordDict`, the remaining prefix "bed" is not.
"beds" is available, but it does not match the beginning of the string.

Constraints

1 <= s.length <= 300

1 <= wordDict.length <= 1000

1 <= wordDict[i].length <= 20

s and wordDict[i] consist of only lowercase English letters.

All the strings of wordDict are unique.

76. Word Break