139. Word Break
You are given a lowercase string s and a list of dictionary words. Decide whether s can be carved into a sequence of one or more dictionary words laid end to end — the same word may be used as many times as you like. Return true if such a segmentation exists, false otherwise.
Beware of greedy choices: grabbing the longest (or shortest) matching prefix first can strand you, so the search has to consider every viable split.
Example 1:
Input: s = "sunflower", words = ["sun", "flower", "flow"]
Output: true
Explanation: "sunflower" splits into "sun" + "flower", both dictionary words.
Example 2:
Input: s = "cartrip", words = ["car", "cart", "rip"]
Output: true
Explanation: "cart" + "rip" works. Note that starting with "car" leaves "trip", which cannot be matched — a greedy first choice would wrongly answer false.
Example 3:
Input: s = "notebooks", words = ["note", "book", "notebook"]
Output: false
Explanation: Every segmentation leaves a dangling "s": "note" + "book" + "s", "notebook" + "s" — no dictionary word covers it.
Constraints:
- 1 ≤ s.length ≤ 300
- 1 ≤ words.length ≤ 1000
- 1 ≤ words[i].length ≤ 20
- s and every word consist of lowercase English letters only
- All dictionary words are distinct.
Hints:
Think in terms of positions: position i is *reachable* if some prefix s[0..i) can be segmented. Position 0 is reachable; you want to know whether position n is.
Plain recursion ("try every dictionary word as the next piece") revisits the same suffix exponentially often. There are only n+1 distinct suffixes — memoize whether each one is breakable.
Bottom-up: dp[i] is true when some j < i has dp[j] true and s[j..i) in the word set. Only look back as far as the longest dictionary word.
To avoid hashing substrings entirely, put the dictionary in a trie and, from each reachable position, walk the trie along s marking every position where a word ends.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "sunflower", words = ["sun", "flower", "flow"]
Expected output: true