707. Can It Be Segmented
A text-to-speech engine has a recorded clip for every word in a small dictionary. Given a recording script s written without spaces and the list words of available clips, decide whether the script can be built by playing clips one after another, so that the clips laid end to end spell exactly s.
Return true if s can be split into consecutive pieces that are all present in words, otherwise return false. A clip may be played any number of times, and it does not matter how many pieces are used. Equal strings inside words are the same clip.
Aim for time about O(n * k * m), where k is the number of distinct clip lengths and m the longest clip, and space O(n + total clip length).
Example 1
- Input:
- s = "sunsetsun", words = ["sun","set","su"]
- Output:
- true
- Explanation:
The script splits as sun + set + sun, and every piece is an available clip.
Example 2
- Input:
- s = "mapmapmat", words = ["map","ma","tap"]
- Output:
- false
- Explanation:
No clip ends with the letter t, so the last letter can never be covered and the answer is false.
Constraints
1 ≤ n = s.length ≤ 5 * 104
1 ≤ words.length ≤ 100, 1 ≤ words[i].length ≤ 20
All strings use lowercase letters.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,400 msC++ 600 msJava 1,200 msJavaScript 1,200 msTypeScript 1,200 ms
Expected complexity
- Time
- O(n * k * m)
- Space
- O(n + total clip length)