Why it works
- A split of the first j letters ends with some word w, and before it the first j − len(w) letters split too. So ok[j] is true exactly when a true cell lies one word before it, and laying every word from every true cell finds them all.
- A true cell is not enough on its own: after sea the rest shell starts with no word, and that branch just stops. The word seas leads to ok[4], and from there hell reaches the end.
- Brute force cuts the string in every possible way, and the ways to continue from the same index are tried again and again. The table answers each index once.
Complexity
Time O(n × words × length of a word): from each of the n positions every word is compared letter by letter. Memory O(n) for the table.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗