Word Break — Reachability DP on String Segmentation

Problem Statement#

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.

Constraints:

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s and all wordDict[i] consist of only lowercase English letters.
• All strings in wordDict are unique.

Example 1:

Input:  s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: "leetcode" can be segmented as "leet code".

Example 2:

Input:  s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: "applepenapple" can be segmented as "apple pen apple" (reusing "apple").

Example 3:

Input:  s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
Explanation: No valid segmentation exists.

Why This Problem Matters#

Word Break (LeetCode 139) is one of the most frequently asked string DP problems across FAANG companies. Amazon, Google, and Microsoft reach for it in phone screens and onsites because it combines three important skills: dynamic programming for reachability, string manipulation and substring extraction, and hash set usage for O(1) word lookup.

The problem is also a canonical example of "reachability DP" — the same pattern used in Jump Game, where dp[i] represents whether position i is "reachable" (here, whether the first i characters can be validly segmented). Recognizing this as a reachability problem (rather than a counting or optimization problem) is the key framing insight.

Word Break II (LC 140) extends this problem to output all valid segmentations, requiring backtracking on top of the DP. Interviewers often ask for Word Break II as a follow-up.

The Core Insight#

Define dp[i] as True if the first i characters of s (s[0..i-1]) can be segmented into dictionary words.

Base case: dp[0] = True — an empty prefix can always be trivially "segmented" (into zero words).

Transition: dp[i] = True if there exists some index j (0 <= j < i) such that:

• dp[j] = True (the first j characters can be validly segmented), AND
• s[j:i] is in the word dictionary (the substring from j to i is a valid word).

If any such j exists, dp[i] = True. Otherwise, dp[i] = False.

The answer is dp[n] where n = len(s).

Why this works: The segmentation of s[0..i-1] ends with some last word s[j..i-1]. Before that word, s[0..j-1] must also be validly segmented — which is exactly dp[j] = True. So the recurrence correctly captures all possible segmentations.

Optimal substructure: Segmenting s[0..i-1] depends on correctly segmenting strictly shorter prefixes.

Overlapping subproblems: Many dp[i] states are reused by multiple larger dp[k] computations.

Building the DP Solution#

Step 1 — Naive Recursion (Exponential)#

# Python — naive recursion, exponential — illustrative only
def wordBreak(s, wordDict):
    words = set(wordDict)
    def dp(start):
        if start == len(s):
            return True
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in words and dp(end):
                return True
        return False
    return dp(0)

// JavaScript — naive recursion
function wordBreak(s, wordDict) {
    const words = new Set(wordDict);
    function dp(start) {
        if (start === s.length) return true;
        for (let end = start + 1; end <= s.length; end++) {
            if (words.has(s.slice(start, end)) && dp(end)) return true;
        }
        return false;
    }
    return dp(0);
}

Without memoization, the same start position is re-evaluated many times. Exponential in the worst case.

Step 2 — Top-Down Memoization (O(n^2) time, O(n) space)#

# Python — top-down memoization
from functools import lru_cache
 
class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        words = set(wordDict)
        n = len(s)
 
        @lru_cache(maxsize=None)
        def dp(start: int) -> bool:
            if start == n:
                return True
            for end in range(start + 1, n + 1):
                if s[start:end] in words and dp(end):
                    return True
            return False
 
        return dp(0)

// JavaScript — top-down memoization
var wordBreak = function(s, wordDict) {
    const words = new Set(wordDict);
    const n = s.length;
    const memo = new Map();
 
    function dp(start) {
        if (start === n) return true;
        if (memo.has(start)) return memo.get(start);
        for (let end = start + 1; end <= n; end++) {
            if (words.has(s.slice(start, end)) && dp(end)) {
                memo.set(start, true);
                return true;
            }
        }
        memo.set(start, false);
        return false;
    }
 
    return dp(0);
};

Step 3 — Bottom-Up Tabulation (O(n^2) time, O(n) space)#

# Python — bottom-up tabulation
class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        words = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True  # empty prefix is always segmentable
 
        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  # early exit once dp[i] is True
 
        return dp[n]

// JavaScript — bottom-up tabulation
var wordBreak = function(s, wordDict) {
    const words = new Set(wordDict);
    const n = s.length;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
 
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && words.has(s.slice(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
 
    return dp[n];
};

Optimized Solution#

The O(n^2) tabulation is the standard optimal solution for this problem. An optimization: if you know the maximum word length max_len in the dictionary, the inner loop only needs to go back max_len positions instead of all the way to 0:

# Python — optimized with max word length bound
class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        words = set(wordDict)
        max_len = max(len(w) for w in wordDict)
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
 
        for i in range(1, n + 1):
            for j in range(max(0, i - max_len), i):
                if dp[j] and s[j:i] in words:
                    dp[i] = True
                    break
 
        return dp[n]

// JavaScript — optimized with max word length bound
var wordBreak = function(s, wordDict) {
    const words = new Set(wordDict);
    const maxLen = Math.max(...wordDict.map(w => w.length));
    const n = s.length;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
 
    for (let i = 1; i <= n; i++) {
        for (let j = Math.max(0, i - maxLen); j < i; j++) {
            if (dp[j] && words.has(s.slice(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
 
    return dp[n];
};

Visual Dry Run#

Input: s = "leetcode", wordDict = ["leet", "code"]

Words set: {"leet", "code"}

Answer: dp[8] = True. Segmentation: "leet" + "code".

Complexity Analysis#

The substring check s[j:i] in words is O(i - j) for string hashing, making the total O(n^2 * max_word_len) in the worst case. For the given constraints (n=300, word lengths ≤ 20), this is very fast.

Common Mistakes#

1. Initializing dp[0] = False. dp[0] = True is the essential base case. Without it, no dp[i] can ever become True because the chain starts from dp[0].

2. Using a list for word lookup instead of a set. Checking word in wordDict (a list) is O(k) where k is the dictionary size. Convert to a set first for O(1) amortized lookup.

3. Starting the inner loop at j = 1 instead of j = 0. The entire prefix s[0:i] might be a dictionary word. Starting at j = 0 allows this case (when dp[0] = True and s[0:i] is in the dictionary).

4. Not breaking early when dp[i] is set. Once dp[i] is True, there is no need to check more j values. Add a break (Python) or early return (top-down) to short-circuit.

5. Confusing Word Break (True/False) with Word Break II (all segmentations). Word Break I is a reachability Boolean DP. Word Break II requires backtracking to collect all valid splits — a fundamentally more expensive problem.

6. Using s[j:i+1] instead of s[j:i]. In Python slicing, s[j:i] gives characters at indices j through i-1 (the i-th character excluded). Using s[j:i+1] shifts the substring by one position.

Interview Tips#

Frame it as reachability. "I define dp[i] as whether the first i characters of s can be segmented. dp[0] is trivially True (empty string). Then dp[i] is True if any dp[j] is True and s[j:i] is in the dictionary."

Use a set immediately. "I convert wordDict to a set first for O(1) word lookup. The bottleneck is the O(n^2) nested loops, not the dictionary lookup."

Mention the max word length optimization. "In practice, I only need to look back max_word_length positions in the inner loop, not all the way to 0. This can significantly improve average-case performance."

Offer Word Break II as a follow-up. "If the interviewer asks how to return all valid segmentations, I would add backtracking on top of this DP — or store a parent array of which j values led to each dp[i] = True."

Follow-up Questions#

Q: How do you return all valid segmentations (Word Break II, LC 140)? Build a parent dictionary: for each dp[i] = True, record all j values that enabled it. Then DFS backward from n, collecting all paths. Time complexity becomes O(2^n) in the worst case (exponential in the number of segmentations).

Q: What if words can overlap positions (e.g., characters can be shared between words)? This problem uses non-overlapping contiguous substrings. Overlapping word placement would require a different model (e.g., trie-based matching).

Q: What if the dictionary is very large and word lookup is expensive? Use a trie (prefix tree) to match multiple words simultaneously from each position. This reduces the lookup to O(max_word_length) regardless of dictionary size.

Q: What if the string contains spaces and you want to verify an existing segmentation? Split on spaces and check each segment against the dictionary. This is O(n) with a set — no DP needed.

Q: What if you want to find the minimum number of words to segment s? Change the DP to dp[i] = minimum words to segment s[0:i]. Initialize dp[0] = 0 and use dp[i] = min(dp[j] + 1) for valid j.

Key Takeaways#

• Reachability DP: define dp[i] = True if s[0:i] can be segmented. Base case: dp[0] = True.
• Transition: dp[i] = True if there exists j < i with dp[j] = True and s[j:i] in the word dictionary.
• Always convert wordDict to a set for O(1) lookup. Never check membership in a list.
• Time O(n^2), Space O(n). Improve the inner loop bound to max_word_length for better practical performance.
• The "break early" optimization stops the inner loop the moment dp[i] is set, avoiding unnecessary work.
• Word Break I (Boolean) and Word Break II (enumerate all segmentations) share the same DP table but differ in output — II requires backtracking, which is exponential in the number of results.