DiffPush Tier Recursion · Try Out All Combos O(n^2) with memoization over offsets (bare source recursion is exponential) · O(n) memo and recursion depth
An industrial controller accepts command strings only when they can be split entirely into tokens from its approved vocabulary — spaces are stripped, so the split points are invisible. The parser scans from the current offset, tries every vocabulary word that matches a prefix there, and recurses on the rest; the command is accepted when some chain of matches consumes the whole string.
Input: A string s and an array wordDict of vocabulary words.
Output: true when s can be segmented entirely into dictionary words, false otherwise.
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s and wordDict[i] consist of lowercase lettersInput: {"s":"leetcode","wordDict":["leet","code"]}
Output: true
"leet" consumes the first four letters and "code" the rest.
Input: {"s":"catsandog","wordDict":["cats","dog","sand","and","cat"]}
Output: false
Both parsings — "cats and" and "cat sand" — strand the trailing "og".