513. Can the String Be Segmented
Given a dictionary of words, print yes if the string can be split into a sequence of
dictionary words, or no otherwise. Words may be reused any number of times, and every
character must be covered.
leetcode, words leet code -> yes
catsandog, words cats dog sand and cat -> no
aaaaaaa, words aaa aaaa -> yes aaa + aaaa
## Why greedy fails
Taking the longest matching word at each position is wrong, and catsandog shows why:
cats matches, then and, then og is not a word. Backing up to cat, then sand,
then og again fails. The answer is no, but the greedy would have to try both to know
that, and on inputs where the answer is yes the greedy can commit to a prefix that
dooms the rest.
aaaaaaa with aaa and aaaa is the positive version: longest-first takes aaaa then
aaa, which works, and shortest-first takes aaa aaa and is then stuck with one a.
Neither order is reliable.
## The recurrence
ok[i] = can the first i characters be segmented
ok[0] = true
ok[i] = true if some j < i has ok[j] and s[j..i-1] is a word
Each position is decided once and reused by every later position, which is what makes this linear in the number of (start, end) pairs rather than exponential in the number of splits. The exponential recursion and this table differ only in that the table remembers.
## Why ok[0] = true is the whole base case
ok[0] says the empty prefix is segmentable, by the empty sequence of words. Every other
entry is built from it, and getting it wrong makes the entire table false.
It is worth being able to say what ok[0] = true MEANS rather than treating it as a magic
initialiser, because the same question decides problem 491's initialisation and gets a
different answer there.
## Implementation notes
Put the dictionary in a hash set, so the membership test is O(length of the candidate)
rather than a scan of the word list.
The inner loop can stop at the longest word length: a candidate longer than every
dictionary word cannot match. That turns O(n^2) substring tests into
O(n * maxWordLength), which matters when n is large and the words are short.
## Boundaries
a with the single word a answers yes, and with the single word b answers no.
Those are the smallest cases in each direction.
abcd with ab abc cd answers yes via ab + cd, and it is the case where the FIRST
matching word at position 0 is not part of any solution if you happened to try abc
first. The table tries all of them.
## Cost
Time O(n * maxWordLength) substring tests, each O(maxWordLength). Space O(n) plus the
dictionary.
Constraints - `1 ≤ k ≤ 1000` - `1 ≤ length of s ≤ 2000` - `1 ≤ length of each word ≤ 100` - all strings contain only lowercase letters
Input
The first line contains an integer k, the number of dictionary words.
The second line contains the string s.
Each of the next k lines contains one dictionary word.
Output
Print yes if the string can be split entirely into dictionary words, or no otherwise.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.