Word Break Problem: Multiple Solutions and Complexity Analysis

Word Break Problem: Multiple Solutions and Complexity Analysis

The Word Break Problem is a classic dynamic programming challenge that frequently appears in coding interviews and real-world text processing applications. Given a string and a dictionary of valid words, the problem asks whether the string can be segmented into a space-separated sequence of one or more dictionary words. In this tutorial, we'll explore multiple approaches to solve it, analyze their complexities, and discuss best practices.

What Is the Word Break Problem?

Formally, you are given an input string s and a dictionary wordDict containing a list of strings. You must return true if s can be segmented into a space-separated sequence of one or more words from wordDict, otherwise false. The same word in the dictionary may be reused multiple times.

For example, given s = "leetcode" and wordDict = ["leet", "code"], the answer is true because "leetcode" can be split into "leet" and "code". However, with s = "catsandog" and wordDict = ["cats", "dog", "sand", "and", "cat"], the answer is false because no valid segmentation exists.

Why It Matters

The Word Break Problem is more than an interview staple. It underpins several practical systems:

• Tokenization in NLP: Segmenting text without spaces (such as Chinese text or compound words) into meaningful tokens.
• Spell checkers and autocomplete: Detecting valid word boundaries in user input.
• URL slugs and search queries: Splitting concatenated keywords into recognizable terms.
• Code obfuscation reversal: Recovering variable names from concatenated identifiers.

Understanding the problem also teaches fundamental algorithmic concepts: recursion with memoization, dynamic programming, and the trade-offs between time and space complexity.

Solution 1: Naive Recursion

The most intuitive approach is to try every possible prefix of the string. If the prefix exists in the dictionary, recursively check the remaining suffix. The base case is an empty string, which is trivially segmentable.

def word_break_naive(s, word_dict):
    word_set = set(word_dict)
    
    def helper(remaining):
        if remaining == "":
            return True
        for i in range(1, len(remaining) + 1):
            prefix = remaining[:i]
            if prefix in word_set and helper(remaining[i:]):
                return True
        return False
    
    return helper(s)

# Example
print(word_break_naive("leetcode", ["leet", "code"]))  # True

Complexity Analysis

The naive recursive solution explores every possible partition of the string. For a string of length n, there are 2^(n-1) possible ways to partition it. Each check involves a substring operation costing O(n). Therefore, the worst-case time complexity is O(n * 2^n), which is exponential. The space complexity is O(n) due to the recursion stack.

This approach is impractical for strings longer than about 20 characters because the number of recursive calls explodes.

Solution 2: Recursion with Memoization (Top-Down DP)

The naive approach recomputes the same subproblems repeatedly. By caching results for each starting index, we eliminate redundant work. This is the top-down dynamic programming approach.

def word_break_memo(s, word_dict):
    word_set = set(word_dict)
    memo = {}
    
    def helper(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 word_set and helper(end):
                memo[start] = True
                return True
        memo[start] = False
        return False
    
    return helper(0)

# Example
print(word_break_memo("leetcode", ["leet", "code"]))  # True
print(word_break_memo("catsandog", ["cats","dog","sand","and","cat"]))  # False

Complexity Analysis

With memoization, each starting index from 0 to n-1 is computed at most once. For each index, we iterate through possible end positions, making the time complexity O(n^2) for the nested loops, plus O(n) for each substring operation, yielding O(n^3) overall. The space complexity is O(n) for the memoization table and recursion stack.

This is a dramatic improvement over the naive approach and works well for strings up to several thousand characters.

Solution 3: Bottom-Up Dynamic Programming

We can convert the memoized solution into an iterative bottom-up DP. Define dp[i] as True if the substring s[0:i] can be segmented. The recurrence is:

dp[i] = True if there exists some j where dp[j] is True and s[j:i] is in the dictionary.

def word_break_dp(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True  # empty string is segmentable
    
    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]

# Example
print(word_break_dp("leetcode", ["leet", "code"]))  # True

Complexity Analysis

The outer loop runs n times, and the inner loop runs up to n times, with each substring check costing O(n) in the worst case. This gives O(n^3) time complexity and O(n) space complexity for the DP array. In practice, if we limit j to the maximum word length in the dictionary, we can reduce the effective time to O(n * L^2) where L is the maximum word length.

Solution 4: Optimized DP with Word Length Pruning

A practical optimization limits the inner loop to only check substrings whose lengths match a word in the dictionary. This avoids checking substrings that cannot possibly match.

def word_break_optimized(s, word_dict):
    word_set = set(word_dict)
    max_len = max((len(w) for w in word_set), default=0)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    
    for i in range(1, n + 1):
        # Only check substrings ending at i with valid lengths
        for j in range(max(0, i - max_len), i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    
    return dp[n]

# Example
print(word_break_optimized("leetcode", ["leet", "code"]))  # True

Complexity Analysis

By restricting the inner loop to max_len iterations, the time complexity becomes O(n * L * L) = O(n * L^2) where L is the maximum word length. When L is small relative to n, this is significantly faster than the standard DP. Space complexity remains O(n).

Solution 5: Breadth-First Search

We can model the problem as a graph traversal. Each index in the string is a node, and an edge from index i to index j exists if s[i:j] is in the dictionary. We perform BFS from index 0 and check if we can reach index n.

from collections import deque

def word_break_bfs(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    visited = set()
    queue = deque([0])
    
    while queue:
        start = queue.popleft()
        if start in visited:
            continue
        visited.add(start)
        for end in range(start + 1, n + 1):
            if s[start:end] in word_set:
                if end == n:
                    return True
                queue.append(end)
    
    return False

# Example
print(word_break_bfs("leetcode", ["leet", "code"]))  # True

Complexity Analysis

BFS visits each index at most once, and for each index, it checks up to n substrings. The time complexity is O(n^3) in the worst case (or O(n * L^2) with length pruning), and space complexity is O(n) for the queue and visited set. BFS can sometimes find a solution faster than DP when a valid segmentation exists early, because it explores by index progression rather than filling the entire DP table.

Solution 6: Using a Trie

For large dictionaries, checking substring membership against a set can be expensive due to repeated hashing. A trie (prefix tree) allows us to scan the string character by character and stop early when no word in the dictionary has the current prefix.

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

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

def word_break_trie(s, word_dict):
    root = build_trie(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[n] = True
    
    # Process from right to left
    for i in range(n - 1, -1, -1):
        node = root
        for j in range(i, n):
            ch = s[j]
            if ch not in node.children:
                break
            node = node.children[ch]
            if node.is_word and dp[j + 1]:
                dp[i] = True
                break
    
    return dp[0]

# Example
print(word_break_trie("leetcode", ["leet", "code"]))  # True

Complexity Analysis

Building the trie takes O(W) where W is the total number of characters across all dictionary words. The DP traversal is O(n * L) where L is the maximum word length, because the trie traversal stops early when a character is not found. Space complexity is O(W + n) for the trie and DP array. This approach shines when the dictionary is large and contains many words with shared prefixes.

Comparison of Solutions

• Naive Recursion: O(n * 2^n) time, O(n) space. Only useful for understanding the problem.
• Memoization: O(n^3) time, O(n) space. Clean and intuitive.
• Bottom-Up DP: O(n^3) time, O(n) space. Avoids recursion limits.
• Optimized DP: O(n * L^2) time, O(n) space. Best for small max word length.
• BFS: O(n^3) time, O(n) space. Fast early termination.
• Trie + DP: O(n * L) time, O(W + n) space. Best for large dictionaries.

Best Practices

When implementing the Word Break Problem in production code, keep the following guidelines in mind:

• Convert the dictionary to a set: Hash-based lookups are O(1) on average, far faster than list scans.
• Prune by maximum word length: If you know the longest word in the dictionary, never check substrings longer than it. This single optimization often reduces runtime by an order of magnitude.
• Prefer iterative DP over recursion: Python's default recursion limit (around 1000) can be exceeded for long strings. Iterative DP avoids this issue entirely.
• Use a trie for large dictionaries: When the dictionary has thousands of words with shared prefixes, a trie reduces both lookup time and memory compared to a flat set.
• Handle edge cases: Empty strings, empty dictionaries, and strings with characters not present in any dictionary word should be handled explicitly to avoid wasted computation.
• Consider returning the actual segmentation: In real applications, you often need the list of words, not just a boolean. Modify the DP to store back-pointers or word boundaries for reconstruction.

Returning the Segmentation

Here is an extension that returns the actual word segmentation rather than just a boolean:

def word_break_segment(s, word_dict):
    word_set = set(word_dict)
    n = len(s)
    dp = [None] * (n + 1)
    dp[0] = []
    
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] is not None and s[j:i] in word_set:
                dp[i] = dp[j] + [s[j:i]]
                break
    
    return dp[n] if dp[n] is not None else []

# Example
print(word_break_segment("leetcode", ["leet", "code"]))
# Output: ['leet', 'code']

Note that this returns the first valid segmentation found. If you need all possible segmentations, you would store lists of segmentations at each index, which increases both time and space complexity significantly.

Conclusion

The Word Break Problem is a foundational example of how dynamic programming transforms an exponential brute-force solution into a polynomial one. We explored six approaches ranging from naive recursion to trie-augmented DP, each with distinct trade-offs in time, space, and implementation complexity. For most interview and production scenarios, the optimized bottom-up DP with word-length pruning offers the best balance of simplicity and performance. When dealing with large dictionaries, the trie-based approach provides superior lookup efficiency. By understanding these solutions and their complexities, you gain not only the ability to solve this specific problem but also transferable skills applicable to a wide range of segmentation, parsing, and dynamic programming challenges.