Word Break

You are given a string s and a list of strings wordDict representing a dictionary of allowed words. Determine whether s can be split into a sequence of one or more dictionary words placed back-to-back with no characters left over.

Return true if such a segmentation exists, and false otherwise.

Rules to keep in mind:

• Words from wordDict may be reused as many times as needed while building the segmentation.
• Every character of s must be covered by exactly one chosen word — no skipping and no overlapping.
• The words in wordDict are not guaranteed to be distinct, and their order does not matter.

Examples

Example 1:

Input: s = "pinecone", wordDict = ["pine", "cone", "pin", "econe"]

Output: true

Explanation:

"pinecone" can be split as "pine" + "cone", and both pieces appear in wordDict.

Example 2:

Input: s = "catsanddog", wordDict = ["cats", "cat", "and", "sand", "dog"]

Output: true

Explanation:

"catsanddog" can be split as "cat" + "sand" + "dog" (note that "cats" + "and" + "dog" also works, but only one valid segmentation is needed).

Example 3:

Input: s = "applepear", wordDict = ["apple", "pea", "ear"]

Output: false

Explanation:

Starting with "apple" leaves "pear", which cannot be fully covered using "pea" or "ear" without leftover or overlap, and no other starting split works either.

Constraints

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and every word in wordDict consist only of lowercase English letters.
• wordDict may contain duplicate words.