Word Break

Problem

You are given a string s and a list of words wordDict. Decide whether s can be split into a sequence of one or more pieces, each of which appears in wordDict. Words from the dictionary may be reused any number of times, and every character of s must belong to exactly one piece. Return True or False.

• s is a lowercase string up to a few hundred characters long.
• wordDict holds up to a thousand distinct lowercase words, each up to about twenty characters.

Examples

• s = "bluesky", wordDict = ["blue", "sky"] → True, split as blue | sky.
• s = "lampshadex", wordDict = ["lamp", "shade", "lam", "pshade"] → False. Every split leaves a stranded x.
• s = "ccccd", wordDict = ["c", "cc"] → False. The d is never covered no matter how the cs are grouped.

Hints

1. Suppose the string can be segmented. Consider the last word in the segmentation. What must be true of the prefix that comes before it?
2. Recursion that tries every possible last word recomputes the same prefixes many times. What is the natural thing to remember?
3. A boolean DP over prefix lengths: ok[i] is true if some j < i has ok[j] true and s[j:i] in the dictionary.