Word Break
Given a string s and a list of dictionary words wordDict, decide whether s can be split into a sequence of one or more dictionary words with nothing left over. Words may be reused as many times as needed, and every character of s must be covered.
Return true if such a segmentation exists, otherwise false.
Constraints: 1 <= s.length <= 300, 1 <= wordDict.length <= 1000, each word has length 1 to 20, all lowercase, and the dictionary contains no duplicates.
Examples
- Input:
- s = "leetcode", wordDict = ["leet", "code"]
- Output:
- true
"leetcode" splits as "leet" + "code".
- Input:
- s = "applepenapple", wordDict = ["apple", "pen"]
- Output:
- true
Splits as "apple" + "pen" + "apple" — reusing a word is allowed.
- Input:
- s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
- Output:
- false
Both openings dead-end: "cats" leaves "andog" and "cat" leaves "sandog"; neither remainder can be fully covered.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.