Given a string s and a dictionary words, return true if s can be split into a sequence of one or more dictionary words, and false otherwise.
The same dictionary word may be used more than once.
Examples
Example 1
- Input
- s = "codeshare", words = ["code", "share"]
- Output
- true
- Why
- "codeshare" is "code" + "share".
Example 2
- Input
- s = "applepenapple", words = ["apple", "pen"]
- Output
- true
- Why
- Words can repeat: "apple" + "pen" + "apple".
Example 3
- Input
- s = "catsandog", words = ["cats", "dog", "sand", "and", "cat"]
- Output
- false
Constraints
1 <= s.length <= 3001 <= words.length <= 1000- All strings contain only lowercase English letters.