Given a string s and a dictionary of words wordDict, return true if s can be split into a sequence of one or more dictionary words with nothing left over. Words may be reused as many times as needed. The whole of s must be consumed — covering most of it is not a segmentation.
Examples
Example 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Example 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: "apple" is used twice; reuse is allowed.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Explanation: every start ("cats"/"cat") strands a middle no word covers.
Example 4:
Input: s = "cars", wordDict = ["car","ca","rs"]
Output: true
Explanation: "ca" + "rs" — the greedy first choice "car" dead-ends.
Constraints
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and every word consist of lowercase English letters; the words are distinct.
Prerequisites
Dynamic programming — being able to say, in one sentence, what a single cell of your table MEANS. Everything else follows from that sentence. Rolling variables: when a state only looks back one or two steps, the table collapses to a couple of numbers.
How to think about it
1. Reachable Prefixes Optimal
Intuition
reachable[i] means "the first i characters can be split into dictionary words". A position is reachable when some earlier reachable position is followed by a dictionary word ending here — so every end position looks back over the starts already proven. Greedy longest-match fails ("cars" as car + s, when ca + rs was the split), which is why the lookback is not optional.
Algorithm
1. Put the dictionary in a set; the empty prefix is reachable. 2. For each end position, scan earlier reachable starts. 3. If the substring between them is a word, mark the end reachable and stop scanning. 4. The answer is whether the whole string is reachable.
Time & Space
Time O(n^2) substring checks against a set. Space O(n) plus the dictionary. Memoised DFS is the same idea upside down.