Solving the Word Break Problem in Python: A Step-by-Step Guide
The Word Break problem is one of the most classic algorithmic challenges you will encounter in coding interviews and competitive programming. At its core, it asks a deceptively simple question: given a string and a dictionary of valid words, can the string be segmented into a space-separated sequence of one or more dictionary words? Despite its simple phrasing, the problem hides rich algorithmic depth, making it an excellent vehicle for learning dynamic programming, memoization, and backtracking.
What Is the Word Break Problem?
Formally, you are given an input string s and a list of strings wordDict representing a dictionary of valid words. You must determine whether s can be segmented into a sequence of words such that every word in the sequence exists in wordDict. Each word from 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". Conversely, given s = "catsandog" and wordDict = ["cats", "dog", "sand", "and", "cat"], the answer is False because no valid segmentation covers the entire string.
Why the Problem Matters
Beyond being a frequent interview question at companies like Google, Amazon, and Meta, the Word Break problem models real-world scenarios. Natural language processing systems use similar logic for tokenization, where raw text must be split into meaningful tokens. Spell checkers, search engines, and autocomplete systems all rely on efficient string segmentation. Understanding this problem also strengthens your grasp of dynamic programming, a technique that applies to countless optimization challenges.
Naive Recursive Approach
The most intuitive solution is recursion. Starting from the beginning of the string, try every possible prefix. If a prefix exists in the dictionary, recursively check whether the remaining suffix can also be segmented. If any recursive call returns true, the original string is segmentable.
def word_break_naive(s, word_dict):
word_set = set(word_dict)
def can_break(start):
if start == len(s):
return True
for end in range(start + 1, len(s) + 1):
if s[start:end] in word_set and can_break(end):
return True
return False
return can_break(0)
# Example usage
print(word_break_naive("leetcode", ["leet", "code"])) # True
While correct, this approach has exponential time complexity. In the worst case, every character can either be a break point or not, leading to O(2^n) recursive calls. For strings longer than about 25 characters, this becomes impractical.
Memoized Recursive Solution
The naive recursion recomputes the same subproblems repeatedly. By caching results for each starting index, we eliminate redundant work. This technique, called memoization, reduces the time complexity to O(n^2 * k), where n is the string length and k is the average word length for substring operations.
def word_break_memo(s, word_dict):
word_set = set(word_dict)
memo = {}
def can_break(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 can_break(end):
memo[start] = True
return True
memo[start] = False
return False
return can_break(0)
print(word_break_memo("applepenapple", ["apple", "pen"])) # True
Notice how the memo dictionary stores whether segmentation is possible from each index. Before recursing, we check the cache, and after computing, we store the result. This small change transforms an exponential algorithm into a polynomial one.
Bottom-Up Dynamic Programming
The memoized solution is top-down. We can also solve the problem bottom-up using a DP array. Define dp[i] as a boolean indicating whether the substring s[0:i] can be segmented. The base case is dp[0] = True, representing the empty string. For each position i, we check every previous position j; if dp[j] is true and s[j:i] is in the dictionary, then dp[i] is true.
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 always 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 # no need to check further once dp[i] is True
return dp[n]
print(word_break_dp("leetcode", ["leet", "code"])) # True
print(word_break_dp("catsandog", ["cats", "dog", "sand", "and", "cat"])) # False
This DP solution runs in O(n^2) time and uses O(n) space. The inner loop checks all possible split points, and the break statement short-circuits once a valid segmentation is found for position i.
Optimizing With Word Length Bounds
A useful optimization limits the inner loop to only check substrings whose lengths match possible dictionary words. By precomputing the maximum word length, we avoid checking impossibly long substrings.
def word_break_optimized(s, word_dict):
word_set = set(word_dict)
if not word_set:
return len(s) == 0
n = len(s)
max_len = max(len(w) for w in word_set)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
# Only check substrings ending at i with length <= max_len
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]
print(word_break_optimized("aaaaaaaaaaaaaaaaaaab", ["a", "aa", "aaa"])) # False
This optimization is particularly valuable when the dictionary contains short words but the input string is long. The worst-case time complexity remains O(n^2), but in practice the constant factor shrinks significantly.
Reconstructing the Segmentation
Sometimes you need not just a boolean answer but the actual word segmentation. We can extend the DP approach to track which split point led to each successful state, then reconstruct the path backward.
def word_break_reconstruct(s, word_dict):
word_set = set(word_dict)
n = len(s)
dp = [False] * (n + 1)
parent = [-1] * (n + 1) # track split points
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
parent[i] = j
break
if not dp[n]:
return []
# Reconstruct the word list
words = []
idx = n
while idx > 0:
words.append(s[parent[idx]:idx])
idx = parent[idx]
words.reverse()
return words
print(word_break_reconstruct("leetcode", ["leet", "code"]))
# Output: ['leet', 'code']
The parent array records the index from which each position was reached. Walking backward from n to 0 collects the words in reverse order, which we then reverse to get the final segmentation.
Handling All Possible Segmentations
A harder variant asks for all possible segmentations rather than just one. This requires backtracking with memoization to avoid exponential blowup while still enumerating every valid path.
def word_break_all(s, word_dict):
word_set = set(word_dict)
memo = {}
def backtrack(start):
if start == len(s):
return [[]]
if start in memo:
return memo[start]
results = []
for end in range(start + 1, len(s) + 1):
word = s[start:end]
if word in word_set:
for sub in backtrack(end):
results.append([word] + sub)
memo[start] = results
return results
return backtrack(0)
print(word_break_all("catsanddog", ["cat", "cats", "and", "sand", "dog"]))
# Output: [['cat', 'sand', 'dog'], ['cats', 'and', 'dog']]
Here the memo stores all valid segmentations starting from each index. This prevents recomputation while still allowing full enumeration. Be cautious: the number of valid segmentations can grow exponentially, so this variant is only feasible when the answer set is small.
Best Practices
- Convert the dictionary to a set first. Set lookups are
O(1)on average, while list lookups areO(k). This single change often yields a massive speedup. - Choose the right algorithm for the input size. For short strings under 20 characters, the naive recursion may suffice. For longer inputs, always use memoization or bottom-up DP.
- Precompute the maximum word length. This bounds the inner loop and avoids checking substrings longer than any dictionary word.
- Handle edge cases explicitly. Empty strings, empty dictionaries, and strings with characters not present in any dictionary word should all be handled gracefully.
- Use iterative DP over recursion for very long strings. Python's default recursion limit is around 1000, so deep recursion on long strings will raise
RecursionError. The bottom-up approach avoids this entirely. - Test with adversarial inputs. Strings like
"aaaaaa...b"with a dictionary of["a", "aa", "aaa"]are classic worst cases. Ensure your solution handles them without timing out.
Common Pitfalls
One frequent mistake is forgetting the base case dp[0] = True. Without it, no segmentation can ever be marked valid because every valid split depends on a previous valid state. Another pitfall is using a list instead of a set for the dictionary, which silently degrades performance. Finally, be careful with substring slicing in Python: s[j:i] creates a new string, and while this is acceptable for most inputs, extremely long strings may benefit from hash-based rolling techniques for further optimization.
Conclusion
The Word Break problem is a perfect showcase for the power of dynamic programming. Starting from a naive exponential recursion, we progressively refined the solution through memoization, bottom-up DP, and length-bounded optimization, ultimately arriving at an efficient O(n^2) algorithm. Along the way, we explored variants that reconstruct the actual segmentation and enumerate all possible segmentations. Mastering this problem not only prepares you for technical interviews but also deepens your understanding of how overlapping subproblems can be tamed through careful state management. Whether you are building a tokenizer, a spell checker, or simply sharpening your algorithmic skills, the techniques demonstrated here will serve you well across a wide range of string-processing challenges.