Can the String Be Split Into Words
Given a string and a list of words, print yes if the string can be cut into a
sequence of those words, and no otherwise. Words may be reused any number of
times.
leetcode with leet code -> yes
catsandog with cats dog sand and cat -> no
Matching the longest word at each step is the obvious greedy and it is wrong.
On catsandog it takes cats, then and, and is left with og, so it reports
failure. Taking cat first leads to sand and then og as well, so this input
is genuinely impossible, but the same greedy fails on inputs that ARE possible:
with words a and ab and bc, the string abc needs a first, and longest-first
takes ab and dies.
So every cut point has to be considered. Let ok(i) mean "the first i
characters can be split":
ok(0) = true
ok(i) = true if for some j < i, ok(j) and s[j..i) is a word
Top-down this is a recursion on the remaining suffix, cached by start index;
bottom-up it is one pass filling ok upwards. Both are O(n^2) substring checks
against a set.
Caching is what makes it polynomial. Without it, a string of as against words
a and aa explores exponentially many identical subproblems.