Word Break Problem: Dynamic Programming Solution

Key Insights

The word break problem exhibits overlapping subproblems, making it a textbook case for dynamic programming optimization that reduces exponential time complexity to O(n²·m)
A bottom-up DP approach using a boolean array where dp[i] represents whether the substring s[0:i] can be segmented provides both clarity and efficiency
Reconstructing actual word segmentations requires tracking split points during the DP pass, enabling backtracking to find all valid decompositions

Introduction & Problem Statement

The word break problem is deceptively simple to state: given a string s and a dictionary of words, determine whether s can be segmented into a sequence of one or more dictionary words. For example, given the string “leetcode” and dictionary [“leet”, “code”], the answer is true because “leetcode” can be split into “leet code”.

This problem appears constantly in real-world systems. Search engines use it for query segmentation when users omit spaces. NLP pipelines apply it to languages like Chinese and Japanese that don’t use whitespace between words. Text processing systems rely on it for hashtag parsing, URL slug interpretation, and autocomplete suggestions. Understanding this problem deeply pays dividends across multiple domains.

What makes word break interesting is the explosion of possibilities. A string of length n has n-1 potential split points, yielding 2^(n-1) possible segmentations to check. Brute force crumbles under this combinatorial weight. Dynamic programming transforms an intractable problem into an elegant, efficient solution.

Understanding the Brute Force Approach

The naive approach uses recursion with backtracking. At each position, we try every possible prefix. If the prefix exists in the dictionary, we recursively check if the remaining suffix can be segmented.

def word_break_recursive(s: str, word_dict: set) -> bool:
    def can_break(start: int) -> bool:
        if start == len(s):
            return True
        
        for end in range(start + 1, len(s) + 1):
            prefix = s[start:end]
            if prefix in word_dict and can_break(end):
                return True
        
        return False
    
    return can_break(0)

This solution is correct but catastrophically slow. Consider the string “aaaaaaaaab” with dictionary [“a”, “aa”, “aaa”, “aaaa”]. Every prefix matches, so we explore every possible combination of a’s before discovering that ‘b’ ruins everything.

The time complexity is O(2^n) in the worst case. Each position branches into multiple recursive calls, and without pruning, we revisit the same subproblems repeatedly. For a 100-character string, this approach is hopeless.

Identifying Overlapping Subproblems

The key insight is recognizing redundant computation. When processing “leetcode”, we might check if “code” is breakable multiple times—once after matching “leet”, and potentially again through other paths.

Let’s trace the recursive calls for “catsanddog” with dictionary [“cat”, “cats”, “and”, “sand”, “dog”]:

can_break(0)  → tries "cat" → can_break(3)
                           → tries "sand" → can_break(7)
                                         → tries "dog" → can_break(10) ✓
              → tries "cats" → can_break(4)
                            → tries "and" → can_break(7)  ← REPEATED!
                                         → tries "dog" → can_break(10) ✓

Notice can_break(7) is called twice. In longer strings with more dictionary matches, this repetition compounds exponentially. The subproblem “can we break the substring starting at index i?” gets solved multiple times with identical results.

This is the hallmark of dynamic programming applicability: overlapping subproblems with optimal substructure. If we cache results, each subproblem is solved exactly once.

Bottom-Up DP Solution

The tabulation approach builds solutions from smaller subproblems to larger ones. We create a boolean array dp where dp[i] is true if the substring s[0:i] can be segmented into dictionary words.

The base case is dp[0] = True—an empty string is trivially segmentable. For each position i, we check all possible last words. If dp[j] is true and s[j:i] is in the dictionary, then dp[i] is true.

def word_break(s: str, word_dict: list) -> bool:
    word_set = set(word_dict)
    n = len(s)
    
    # dp[i] = True if s[0:i] can be segmented
    dp = [False] * (n + 1)
    dp[0] = True  # empty string base case
    
    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  # found valid segmentation, no need to continue
        
    return dp[n]

Here’s the equivalent in JavaScript:

function wordBreak(s, wordDict) {
    const wordSet = 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] && wordSet.has(s.slice(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    
    return dp[n];
}

Walking through “leetcode” with dictionary [“leet”, “code”]:

i	Substring checked	dp[i]
0	"" (base)	true
1-3	No matches	false
4	“leet” (dp[0]=true)	true
5-7	No valid splits	false
8	“code” (dp[4]=true)	true

The final answer is dp[8] = true.

Reconstructing the Segmentation

Returning true/false is useful, but many applications need the actual words. We modify our approach to track which words led to each valid state, then backtrack to reconstruct all segmentations.

def word_break_all(s: str, word_dict: list) -> list:
    word_set = set(word_dict)
    n = len(s)
    
    # dp[i] stores list of indices j where s[j:i] is a valid word
    # and dp[j] was reachable
    dp = [[] for _ in range(n + 1)]
    dp[0] = [-1]  # sentinel: empty string is reachable
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i].append(j)
    
    # Backtrack to find all segmentations
    def backtrack(end: int) -> list:
        if end == 0:
            return [[]]
        
        results = []
        for start in dp[end]:
            word = s[start:end]
            for path in backtrack(start):
                results.append(path + [word])
        
        return results
    
    return [' '.join(words) for words in backtrack(n)]


# Example usage
s = "catsanddog"
word_dict = ["cat", "cats", "and", "sand", "dog"]
print(word_break_all(s, word_dict))
# Output: ['cat sand dog', 'cats and dog']

This approach stores all valid split points rather than just a boolean, enabling complete reconstruction. The backtracking phase traverses these stored indices to build every valid segmentation.

Complexity Analysis & Optimizations

The bottom-up solution has time complexity O(n² · m), where n is the string length and m is the average time for dictionary lookup and substring creation. With a hash set, lookup is O(1) amortized, but substring creation is O(k) for a substring of length k. Space complexity is O(n) for the DP array.

Several optimizations improve practical performance:

1. Limit word length checks: Most dictionaries have a maximum word length. Skip iterations where i - j exceeds this limit.

def word_break_optimized(s: str, word_dict: list) -> bool:
    word_set = set(word_dict)
    max_word_len = max(len(w) for w in word_dict) if word_dict else 0
    n = len(s)
    
    dp = [False] * (n + 1)
    dp[0] = True
    
    for i in range(1, n + 1):
        # Only check substrings up to max word length
        for j in range(max(0, i - max_word_len), i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    
    return dp[n]

2. Trie-based lookup: For large dictionaries, a Trie enables checking all possible words starting at position j in a single traversal.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

def build_trie(words):
    root = TrieNode()
    for word in words:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True
    return root

def word_break_trie(s: str, word_dict: list) -> bool:
    root = build_trie(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    
    for i in range(n):
        if not dp[i]:
            continue
        
        node = root
        for j in range(i, n):
            if s[j] not in node.children:
                break
            node = node.children[s[j]]
            if node.is_word:
                dp[j + 1] = True
    
    return dp[n]

This reduces redundant character comparisons when multiple dictionary words share prefixes.

Practice Problems & Variations

Once you’ve mastered the basic word break problem, tackle these variations:

Word Break II (LeetCode 140): Return all possible segmentations. Use the reconstruction approach shown above, but beware of worst-case exponential output size.

Concatenated Words (LeetCode 472): Find all words in a list that can be formed by concatenating other words from the same list. Apply word break to each candidate, excluding itself from the dictionary.

Minimum Word Count Segmentation: Find the segmentation using the fewest words. Modify the DP to track minimum word count instead of boolean reachability.

Extra Characters in a String (LeetCode 2707): Minimize leftover characters that don’t form dictionary words. Track minimum waste instead of boolean feasibility.

Each variation builds on the core DP structure while tweaking the state definition or transition logic. The pattern recognition skills transfer directly.

The word break problem exemplifies why dynamic programming is essential in your algorithmic toolkit. Recognizing the overlapping subproblems, defining the right state, and building solutions incrementally transforms an exponential nightmare into a polynomial-time solution. Master this pattern, and you’ll see it everywhere.