String Segmentation Is Just a DP Reachability Problem: Solving Word Break

"leetcode" -> can you split this into dictionary words? Two seconds of staring and the answer is obvious: "leet" + "code". But write a function that answers the same question for any string and any dictionary, and the naïve approach collapses almost immediately.

The key insight — the one that makes Word Break a DP problem and not a string puzzle — is that you're not searching for a global decomposition. You're asking a local reachability question at every index: can I reach position i using valid words? Once you frame it that way, the three approaches fall out in order of sophistication.

What the constraints force

s.length <= 300, wordDict.length <= 1000, wordDict[i].length <= 20. Let those sit for a moment.

The substring length cap of 20 is important. It means at each position i, you only need to look back at most 20 characters to find a word that could end here — not all the way back to position 0. That bound makes the O(n^2) DP feel generous. Even with n = 300, the inner loop visits at most 300 × 300 = 90,000 pairs, and each substring lookup in a hash set is O(word_length) which tops out at 20. The total work is bounded and perfectly manageable.

An O(2^n) brute-force is a different story. With n = 300, that number has 90 digits. You're not waiting for that to finish.

Brute-force recursion

The most direct reading: stand at index start, try every word in the dictionary, see if it matches the string starting here, and if it does, recurse on the remainder.

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        def backtrack(start: int) -> bool:
            if start == len(s):
                return True
            for word in wordDict:
                if s[start:].startswith(word):
                    if backtrack(start + len(word)):
                        return True
            return False
 
        return backtrack(0)

public class Solution {
    public bool WordBreak(string s, IList<string> wordDict) {
        return Backtrack(s, wordDict, 0);
    }
 
    private bool Backtrack(string s, IList<string> wordDict, int start) {
        if (start == s.Length) return true;
        foreach (string word in wordDict) {
            if (start + word.Length <= s.Length &&
                s.Substring(start, word.Length) == word) {
                if (Backtrack(s, wordDict, start + word.Length))
                    return true;
            }
        }
        return false;
    }
}

This works for small inputs. The problem is backtrack(start) can be called from multiple parent frames — every time a valid word-prefix ends at the same position. With s = "aaaa..." and wordDict = ["a", "aa", "aaa"], the call tree fans out exponentially. Same subproblem, computed many times.

Time: O(2^n) in the worst case. Space: O(n) stack depth.

Memoization: kill the repeated work

The recursion structure is right; the repeated subproblems are wrong. The fix is caching: once you've determined whether backtrack(i) is True or False, store the result and return it immediately on the next visit.

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        word_set = set(wordDict)
        memo: dict[int, bool] = {}
 
        def dfs(start: int) -> bool:
            if start in memo:
                return memo[start]
            if start == len(s):
                return True
            for word in word_set:
                if s[start:start + len(word)] == word:
                    if dfs(start + len(word)):
                        memo[start] = True
                        return True
            memo[start] = False
            return False
 
        return dfs(0)

public class Solution {
    private Dictionary<int, bool> _memo = new();
 
    public bool WordBreak(string s, IList<string> wordDict) {
        _memo.Clear();
        var wordSet = new HashSet<string>(wordDict);
        return Dfs(s, wordSet, 0);
    }
 
    private bool Dfs(string s, HashSet<string> wordSet, int start) {
        if (_memo.TryGetValue(start, out bool cached)) return cached;
        if (start == s.Length) return true;
        foreach (string word in wordSet) {
            if (start + word.Length <= s.Length &&
                s.Substring(start, word.Length) == word) {
                if (Dfs(s, wordSet, start + word.Length)) {
                    _memo[start] = true;
                    return true;
                }
            }
        }
        _memo[start] = false;
        return false;
    }
}

The word_set conversion matters here. Iterating wordDict as a list to check membership is O(|wordDict|) per call; using a set to look up individual words by substring slice is still O(word_length), but iteration over the set to find candidate words is the same O(|wordDict|). Either way, once each start index is computed exactly once, the total subproblems are n and each does O(|wordDict| × max_word_len) work.

Time: O(n × |wordDict| × max_word_len). Space: O(n) for memo, plus O(n) call stack.

The call stack is the issue I'd flag in production. With n = 300 and a word dictionary where only single characters match, the recursion depth can hit 300. Python's default limit is 1000, so you'd survive — but the number makes me nervous. In pathological cases you'd need sys.setrecursionlimit and the stack frames add memory overhead the bottom-up version avoids entirely.

Bottom-up tabulation: the version I'd ship

Flip direction. Instead of asking "can I reach the end from here?", ask "is position i reachable from any earlier valid position?". Define dp[i] as True if the prefix s[0:i] can be segmented into dictionary words.

Base case: dp[0] = True. An empty prefix requires zero words and is trivially valid.

Transition: dp[i] = True if there exists some j < i where dp[j] = True and s[j:i] is in the word set.

s = "leetcode", wordDict = {"leet", "code"}

dp = [T, F, F, F, F, F, F, F, F]
      0  1  2  3  4  5  6  7  8

i=1: j=0 -> dp[0]=T, s[0:1]="l"? No.  dp[1]=F
i=2: j=0 -> "le"? No. j=1 -> dp[1]=F, skip.  dp[2]=F
i=3: j=0 -> "lee"? No. dp[3]=F
i=4: j=0 -> dp[0]=T, s[0:4]="leet"? YES -> dp[4]=T
i=5: j=0 -> "leetc"? No. j=4 -> dp[4]=T, s[4:5]="c"? No. dp[5]=F
i=6: j=4 -> dp[4]=T, s[4:6]="co"? No. dp[6]=F
i=7: j=4 -> s[4:7]="cod"? No. dp[7]=F
i=8: j=4 -> dp[4]=T, s[4:8]="code"? YES -> dp[8]=T

Answer: dp[8] = True

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        word_set = 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 word_set:
                    dp[i] = True
                    break
 
        return dp[n]

public class Solution {
    public bool WordBreak(string s, IList<string> wordDict) {
        var wordSet = new HashSet<string>(wordDict);
        int n = s.Length;
        bool[] dp = new bool[n + 1];
        dp[0] = true;
 
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.Contains(s.Substring(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
 
        return dp[n];
    }
}

No call stack. No dictionary allocation per frame. The dp array is 301 booleans. Memory footprint is tiny.

Time: O(n^2 × max_word_len) — the inner loop over j runs up to n times per i, and each s[j:i] lookup in a hash set hashes the substring in O(i - j) time. In practice i - j rarely reaches 300 because the word length cap is 20, so the effective cost is closer to O(n × max_word_len × n) but bounded by the 20-character ceiling. Space: O(n + |wordDict|) for the dp array and word set.

The dashed edge shows that if "leetcode" were a single dictionary word, dp[8] would be reachable directly from dp[0] — the algorithm would find it on the j=0 iteration at i=8. The solid path shows the actual route through "leet" + "code".

A tighter inner loop when word lengths are bounded

Because wordDict[i].length <= 20, you can replace the j loop from 0 to i with a loop from max(0, i - 20) to i. At n = 300 this barely matters, but it's worth knowing the optimization exists for problems where the string can be much longer. The structure is the same; the constant improves.

Edge cases

s cannot be segmented (s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]): dp[7] becomes True via "cats"+"dog" (positions 0-4-7) but dp[9] never becomes True because "og" is not in the dictionary. The function returns dp[9] = False. The partial segmentation doesn't matter — what matters is that no j satisfies both dp[j] = True and s[j:9] in word_set.

Reused words (s = "applepenapple", wordDict = ["apple", "pen"]): the DP finds dp[5] = True (apple), dp[8] = True (pen), dp[13] = True (apple again). The same word appearing twice in the segmentation is handled automatically because the lookup is against a set with no usage counter.

Single-character string that matches (s = "a", wordDict = ["a"]): dp[1] = True because dp[0] = True and s[0:1] = "a" is in the set. Trivial, but confirms the base case wiring is right.

Word longer than string (wordDict = ["toolong"], s = "short"): s.Substring(j, i - j) where i - j > s.Length - j is guarded by the i <= n outer loop and j < i inner condition, so the substring is always valid. The word "toolong" simply never matches any valid s[j:i] slice.

Approach comparison

W = |wordDict|, L = max word length, n = s.length.

The reachability pattern and where it shows up again

Word Break is a boolean reachability problem dressed in string clothing. The mental model — dp[i] is True if any previous True position j has a valid "hop" to i — appears in a cluster of problems that are structurally identical once you strip the surface framing.

LeetCode 140 (Word Break II) asks for all valid segmentations, not just whether one exists. The dp table becomes a backtracking structure — at each True position you store which j values enabled it, then reconstruct paths. The reachability logic is the same; the output format changes.

LeetCode 472 (Concatenated Words) runs Word Break as a subroutine: a word in the list is "concatenated" if it can be split into other words from the same list. You run wordBreak on each candidate with the remaining words as the dictionary.

LeetCode 91 (Decode Ways) is the count variant: dp[i] becomes an integer (number of ways to decode s[0:i]), the hop is one or two characters (valid digit or valid two-digit code), and the transition sums instead of OR-ing. Same bottom-up table, different semantics.

LeetCode 132 (Palindrome Partitioning II) asks for the minimum cuts to partition a string into palindromes. The "can this substring be a palindrome" check replaces the "is this substring in the dictionary" check, and the table stores a cut count instead of a boolean. The outer structure is the same.

The coin change problem in this series is the closest structural twin: dp[amount] = True/min if any dp[amount - coin] is True/finite. Same hop-from-previous-state logic. The only difference is that Coin Change hops backward by coin denominations and Word Break hops backward by word lengths. If that observation clicks, you'll recognize this family of problems on sight.