Word Break
Last Updated: March 28, 2026
Understanding the Problem
We have a string and a dictionary. The question is whether we can break the string into pieces where every piece is a word in the dictionary. We can reuse words as many times as we want, and we need to cover the entire string with no characters left over.
This is fundamentally a decision problem: can we find at least one valid segmentation? We don't need to return the actual segmentation, just true or false.
The key observation is that this has overlapping subproblems. If we know whether the substring from index i to the end can be segmented, we can reuse that answer when checking different ways to reach index i. That's a strong hint toward dynamic programming.
Key Constraints:
1 <= s.length <= 300-- With n up to 300, O(n^2) gives us 90,000 operations, and O(n^3) gives 27 million. Both are comfortable. But brute force recursion without memoization is O(2^n), which would be far too slow.1 <= wordDict.length <= 1000-- The dictionary can be large, so converting it to a hash set for O(1) lookups is important.1 <= wordDict[i].length <= 20-- Word lengths are short. We only need to check substrings of length up to 20 at each position, which can optimize the inner loop.
Approach 1: Brute Force (Recursion)
Intuition
The most natural way to think about this: start at the beginning of the string and try every possible first word. If the substring s[0..k] matches a dictionary word, then recursively check whether the remaining string s[k+1..end] can also be segmented. If any branch succeeds, return true. If no branch works, return false.
This is essentially exploring a decision tree. At each position in the string, we branch into all dictionary words that match starting at that position. We're looking for any path through this tree that consumes the entire string.
Algorithm
- Convert
wordDictto a hash set for O(1) lookups. - Define a recursive function
canBreak(start)that returns true ifs[start..end]can be segmented. - Base case: if
start == s.length(), we've consumed the entire string, so return true. - For each end index from
start + 1tos.length(), check if the substrings[start..end-1]is in the word set. - If it is, recursively call
canBreak(end). If that returns true, return true. - If no substring works, return false.
Example Walkthrough
Code
- Time Complexity: O(2^n). In the worst case, at every position we branch into multiple recursive calls, and the same subproblems get solved repeatedly. The recursion tree grows exponentially.
- Space Complexity: O(n). The recursion stack goes at most n levels deep.
The same suffix gets checked multiple times through different segmentation paths. What if we stored the result for each starting index the first time we computed it?
Approach 2: Top-Down DP (Recursion + Memoization)
Intuition
The brute force recursion does a lot of duplicate work. The function canBreak(start) only depends on the starting index, and there are only n possible starting indices (0 through n-1). So if we cache the result of canBreak(start) the first time we compute it, every subsequent call with the same start returns immediately.
This is the classic memoization pattern. Same recursive logic, but with a memo table that stores whether each suffix can be segmented. The recursion tree collapses from exponential to linear in the number of unique subproblems.
Algorithm
- Convert
wordDictto a hash set for O(1) lookups. - Create a memo array of size
n + 1, initialized to "unvisited" (use -1 or null to distinguish from true/false). - Define
canBreak(start)the same as before, but before computing, check the memo. If we've already solved this subproblem, return the cached result. - After computing, store the result in the memo before returning.
Example Walkthrough
Code
- Time Complexity: O(n^3). There are n unique subproblems, each trying up to n end positions, with O(n) substring operations. Total: O(n n n).
- Space Complexity: O(n). The memo array and recursion stack each use O(n) space.
The recursion adds overhead from function calls and stack frames. What if we computed the subproblems in a natural bottom-up order, eliminating recursion entirely?
Approach 3: Bottom-Up DP
Intuition
Instead of recursion, we can fill a DP table iteratively. Define dp[i] as "can the first i characters of s be segmented using the dictionary?" The answer we want is dp[n], where n is the length of s.
The recurrence is straightforward: dp[i] is true if there exists some j < i such that dp[j] is true AND the substring s[j..i-1] is in the dictionary. In other words, we can form the first i characters if we can form the first j characters AND the remaining chunk from j to i is a valid word.
The bottom-up DP builds the solution incrementally. dp[0] = true is our anchor: the empty prefix is always valid. Then for each position i, we check all possible "last words" that could end at position i. If any of those last words starts at a position j where dp[j] is already true, then we can form the first i characters by extending a valid segmentation of the first j characters with the word s[j..i-1].
The break statement is important for efficiency: once we find one valid split point j for position i, we don't need to check other values of j. We only need to know that at least one valid segmentation exists.
Algorithm
- Convert
wordDictto a hash set for O(1) lookups. - Create a boolean array
dpof sizen + 1, initialized to false. - Set
dp[0] = true(empty string can always be segmented). - For each position
ifrom 1 to n: - For each position
jfrom 0 toi - 1: - If
dp[j]is true ands[j..i-1]is in the word set, setdp[i] = trueand break. - Return
dp[n].
Example Walkthrough
Code
- Time Complexity: O(n^3). The outer loop runs n times, the inner loop up to n times per iteration, and each substring operation is O(n). In practice, the break and short word lengths make this much faster.
- Space Complexity: O(n). The DP array uses O(n) space. The hash set for the dictionary uses O(m * L) additional space.