Word Break
Problem
Given a string s and a list of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words from wordDict, and false otherwise.
- 1 ≤ s.length ≤ 300
- 1 ≤ wordDict.length ≤ 1000
- 1 ≤ wordDict[i].length ≤ 20
- s and wordDict[i] consist of only lowercase English letters
- All the strings of wordDict are unique
Example
s = "leetcode", wordDict = ["leet", "code"]trueThe string "leetcode" can be segmented as "leet code". The algorithm starts at index 0 and tries prefixes: "l", "le", "lee", "leet". When it finds "leet" in the dictionary, it recursively checks the substring starting at index 4. From index 4, it finds "code" in the dictionary, and the recursion reaches the end of the string, returning true. This confirms the entire string can be segmented.
Approach
Straightforward Solution
A brute-force approach tries every possible prefix at each index and recursively checks the suffix, leading to exponential time complexity due to repeated computations of the same substrings.
Core Observation
The problem asks if the string can be segmented into dictionary words, which naturally breaks down into checking if prefixes are valid words and if the remaining suffix can also be segmented. This exhibits optimal substructure and overlapping subproblems, making it a prime candidate for dynamic programming.
Path to Optimal
PreviewRecognizing the overlapping subproblems, memoization caches results for each starting index to avoid redundant work. The problem is modeled as a top-down recursion with memoization, where dp(i) returns whether the substring s[i:] can be segmented…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a recursive function dp(i) that returns true if s[i:] can be segmented. For each index i, iterate over possible end indices j, check if s[i:j+1] is in the dictionary, and recursively check dp(j+1)…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n^3)
There are O(n) states (starting indices), and for each state, up to O(n) substrings are checked, with substring extraction and dictionary lookup costing O(n) in the worst case, resulting in O(n^3) time.
Space
O(n)
The memoization dictionary stores results for each index, requiring O(n) auxiliary space. The recursion stack depth is at most O(n). The input dictionary is not counted as auxiliary space.
Pattern Spotlight
Dynamic Programming (Top-Down Memoization)
When a problem involves checking all prefixes or suffixes with overlapping subproblems, use recursion with memoization to cache intermediate results and avoid exponential recomputation.
Solution
| 1 | class Solution:
|
| 2 | def wordBreak(self, s: str, wordDict: list[str]) -> bool:
|
| 3 | memo = {}
|
| 4 | word_set = set(wordDict)
|
| 5 |
|
| 6 | def dp(i):
|
| 7 | if i == len(s):
|
| 8 | return True
|
| 9 | if i in memo:
|
| 10 | return memo[i]
|
| 11 |
|
| 12 | for j in range(i, len(s)):
|
| 13 | prefix = s[i : j + 1]
|
| 14 | if prefix in word_set and dp(j + 1):
|
| 15 | memo[i] = True
|
| 16 | return True
|
| 17 |
|
| 18 | memo[i] = False
|
| 19 | return False
|
| 20 |
|
| 21 | return dp(0) |
Step-by-Step Solution
Initialize Memoization Cache and Dictionary Set
| 3 | memo = {}
|
| 4 | word_set = set(wordDict)
|
Objective
To prepare data structures for efficient lookup and caching of intermediate results.
Key Insight
Converting the word dictionary list into a set enables O(1) average-time membership checks, which is crucial for performance when checking prefixes. The memo dictionary caches results for each starting index, preventing repeated recursive calls on the same substring and drastically reducing time complexity.
Interview Quick-Check
Core Logic
Using a set for wordDict allows constant-time prefix membership checks, which is essential for efficient pruning.
Complexity
Memoization ensures each substring starting index is computed once, reducing the recursion tree size from exponential to linear in n.
Recursively Explore Prefixes and Memoize Results
To determine if the substring starting at index i can be segmented by exploring all prefixes and recursively checking suffixes.
Return Final Segmentation Result from Start of String
To initiate the recursive segmentation check from the beginning of the string and return the overall result.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
if prefix in word_set and dp(j + 1):Check if prefix is in the dictionary and recursively check suffix starting at j+1.
This line embodies the problem's optimal substructure by combining prefix validity and recursive suffix segmentation, forming the fundamental recursive decision that enables the DP solution.
memo = {}Initialize a memoization dictionary to cache results for substring start indices.
Memoization is essential to avoid redundant recursive calls on the same substring, reducing exponential complexity to polynomial time.
if i == len(s):Return true if the starting index reaches the end of the string.
Reaching the end means the entire string has been successfully segmented, serving as the base case for recursion.
Full line-by-line criticality + rationale for all 14 lines available on Pro.
Test Your Understanding
Why is memoization critical in this recursive solution for Word Break?
See the answer with Pro.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Word Break from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Word Break drill