Can the Text Be Split Into Dictionary Words?
You get a string text and an array words of different, non-empty words. All letters are lowercase English letters.
Return true if you can cut text into one or more pieces so that every piece is a word in words. Otherwise return false.
- Every character of
textmust belong to exactly one piece. - The same word may be used many times.
- You do not need to use every word.
Hint
Let ok[i] be true when the first i characters can be cut into words. ok[0] is true. ok[i] is true if some word ends exactly at position i and ok is true where that word starts. Taking the longest word that fits first can fail.
Examples
Example 1
- Input:
- "redcarpet", ["red","car","pet","carp","et"]
- Output:
- true
Cut it as "red" + "car" + "pet". The cut "red" + "carp" + "et" also works.
Example 2
- Input:
- "sunbowl", ["sun","bow","owl"]
- Output:
- false
"sun" + "bow" leaves "l", which is not a word. Using "owl" at the end needs "sunb" before it, and "sunb" cannot be cut into words. So no cut covers the whole text.
Example 3
- Input:
- "abab", ["ab"]
- Output:
- true
The word "ab" is used twice.
Constraints
1 <= text.length <= 201 <= words.length <= 81 <= words[i].length <= 5- All words are different.
Run checks your code against the 3 examples. Submit checks it against all 243 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.