An old ticker tape printed words with no spaces. Given the tape s and a list words of vocabulary entries, return True if s can be split into a sequence of vocabulary words (each word may be reused any number of times) and False otherwise. The empty tape can always be split.
Examples
Input: s = "bakeoff", words = ["bake", "off", "ba", "keoff"]
Output: True
Explanation: "bake" + "off" (or "ba" + "keoff").
Input: s = "bakeoffs", words = ["bake", "off", "ba", "keoff"]
Output: False
Constraints
- Target complexity: O(n * L) time where L is the longest word.
Goals
- Mark reachable prefix lengths instead of recomputing substrings
- Bound the inner loop by the longest dictionary word