# The trick to Word Break is spotting the repeated work Source: https://www.techinterview.org/post/3233476084/word-break-memoized-recursion-dp/ Updated: 2026-07-02 ยท techinterview.org Give a candidate `s = "leetcode"` with `wordDict = ["leet", "code"]` and ask whether the string splits cleanly into dictionary words, and most people write the recursion in about ninety seconds. Then you hand them `s = "aaaaaaaaaaaaaaaaab"` against a dictionary of `["a", "aa", "aaa", "aaaa"]` and watch the same solution hang. That gap is the whole interview. The recursion was already correct; the missing piece is remembering answers you have computed before. Word Break (LeetCode 139) shows up at Meta, Amazon, Audible, and a lot of mid-size shops precisely because it looks like a string problem and pays out like a dynamic programming problem. The prompt: return `true` if `s` can be segmented into a space-separated sequence of one or more words from the dictionary, and a word may be reused as many times as you want. ## Ask whether words repeat before you write anything Before writing anything, say two constraints out loud. Can the same dictionary word be reused? For 139 the answer is yes, and it changes nothing about the recursion, but naming it shows you actually read the problem. And how large is the dictionary, how long are the words? If someone hands you a hundred thousand words against a three-hundred-character string, the naive substring approach carries a cost you will be asked to defend later. ## The recursion, and why it's exponential without help The natural framing: to segment `s` starting at index `i`, try every dictionary word that matches at `i`, then recurse on the remainder. If any branch reaches the end of the string, the answer is true. ``` def wordBreak(s, wordDict): words = set(wordDict) def canBreak(start): if start == len(s): return True for end in range(start + 1, len(s) + 1): if s[start:end] in words and canBreak(end): return True return False return canBreak(0) ``` This is correct and it will time out. The reason is that `canBreak(start)` gets called with the same `start` over and over through different prefix paths. On the `"aaaa...b"` input, every prefix built from a's leads back to the same suffixes, so the number of calls grows exponentially in the length of the string. You are recomputing identical subproblems, which is the tell that a cache belongs here. ## A memo table collapses the blowup The subproblem is fully described by one number, the start index. There are only `n + 1` distinct start indices, so the first time you compute `canBreak(start)`, store the result and hand it back on every later call. ``` def wordBreak(s, wordDict): words = set(wordDict) memo = {} def canBreak(start): if start == len(s): return True if start in memo: return memo[start] for end in range(start + 1, len(s) + 1): if s[start:end] in words and canBreak(end): memo[start] = True return True memo[start] = False return False return canBreak(0) ``` Same logic, one memo added, and the exponential blowup disappears. Each of the `n` start positions does at most `O(n)` work picking an end, which puts you at `O(n^2)` transitions before you account for the substring check. That last part matters more than most candidates admit, and it is the next thing worth looking at. ## The bottom-up version interviewers half-expect Memoized recursion and the iterative table are the same computation running in opposite directions. If you would rather not recurse, define `dp[i]` as "the first `i` characters of `s` can be segmented." `dp[0]` is true because the empty string is trivially segmentable. For each position `i`, look backward for a split point `j` where `dp[j]` is already true and `s[j:i]` is a word. ``` def wordBreak(s, wordDict): words = set(wordDict) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in words: dp[i] = True break return dp[n] ``` Reach for this when you want the whole reachability picture in one array, or when recursion depth worries you on a very long string. The answer lives in `dp[n]`. Nothing here beats the memoized recursion on speed; it is the same big-O with different bookkeeping. ## The substring cost nobody writes on the whiteboard People confidently call this `O(n^2)` and stop. Look again at `s[j:i] in words`. Slicing that substring is `O(n)` on its own, and hashing it for the set lookup is another `O(n)`. With two nested loops that is `O(n^3)` in the worst case, not `O(n^2)`. On the short strings LeetCode feeds you it will not matter, but a sharp interviewer will ask, and the accurate answer scores better than the rehearsed one. Two ways to shrink it. Bound the inner loop by the longest word in the dictionary, since any candidate longer than that can never match. When the words are short, that collapses the middle loop toward a constant. The other way drops substrings entirely and is worth knowing cold. ## When the dictionary is huge, walk a trie Building a substring and hashing it for every `(j, i)` pair throws away the fact that words share prefixes. Put the dictionary in a trie and, from each start index, walk the string character by character through the trie. Every time you land on a node that ends a word, you have found a valid split without ever constructing a substring. ``` def wordBreak(s, wordDict): trie = {} for w in wordDict: node = trie for ch in w: node = node.setdefault(ch, {}) node["$"] = True n = len(s) dp = [False] * (n + 1) dp[0] = True for start in range(n): if not dp[start]: continue node = trie for i in range(start, n): ch = s[i] if ch not in node: break node = node[ch] if "$" in node: dp[i + 1] = True return dp[n] ``` The walk stops the moment the current stretch of characters stops matching any word, which prunes a lot of dead branches on real inputs. It pays off when the dictionary is large and the words share long prefixes. For the small dictionaries LeetCode usually gives you, the set version is shorter and plenty fast, so keep the trie in your pocket for the follow-up rather than leading with it. | Approach | Worst-case time | Extra space | Reach for it when | | --- | --- | --- | --- | | Plain recursion | Exponential | O(n) call stack | Never ship it; it is the opening sketch | | Memoized recursion | O(n^2) transitions, O(n^3) counting the substring work | O(n) | Default answer, cleanest to write | | Bottom-up dp array | Same as memoized | O(n) | You want full reachability or fear recursion depth | | Trie plus dp | O(n * L), L is the longest word | O(characters in the dictionary) | Large dictionary with shared prefixes | ## Word Break II is where the follow-up usually goes Once you have a clean 139, the natural escalation is LeetCode 140: return every possible sentence, rather than only whether one exists. The instinct to reuse memoization is right, but the payload changes from a boolean to a list of all completions from a given index, and that list can be exponential. `s = "aaaaaa"` with dictionary `["a", "aa", "aaa"]` has a segmentation count that explodes with length, so no algorithm returns them quickly; the output itself is enormous. The move that separates a strong answer here: run the 139 feasibility check first, or fold it into the memo so a suffix that cannot be segmented returns an empty list at once. Skip that guard and you grind through dead branches on inputs like `"aaaaaaaaaab"` against a dictionary with no `"b"`, building partial sentences that lead nowhere. Interviewers who reach for 140 are usually watching for exactly that pruning reflex. The reason this one stays on interview lists is that it separates candidates who pattern-match "string splitting" from candidates who notice the same suffix getting solved a dozen times. Get to the memo and you have shown the thing they are testing. Everything after that, the table, the trie, the sentence reconstruction, is just how hard the interviewer wants to push.