Ticker Tape Split

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

• 0 <= len(s) <= 3 * 10**4, lowercase letters
• 1 <= len(words) <= 1000, 1 <= len(words[i]) <= 10
• 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