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
Recognizing 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. By storing results, the algorithm reduces exponential complexity to polynomial time.
Optimal Approach
Use 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). Memoize results to avoid recomputation. Return dp(0) as the final answer.
Time
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) |
| 1 | import java.util.*; |
| 2 | |
| 3 | public class Solution { |
| 4 | public boolean wordBreak(String s, List<String> wordDict) { |
| 5 | Map<Integer, Boolean> memo = new HashMap<>(); |
| 6 | Set<String> wordSet = new HashSet<>(wordDict); |
| 7 | |
| 8 | return dp(0, s, wordSet, memo); |
| 9 | } |
| 10 | |
| 11 | private boolean dp(int i, String s, Set<String> wordSet, Map<Integer, Boolean> memo) { |
| 12 | if (i == s.length()) { |
| 13 | return true; |
| 14 | } |
| 15 | if (memo.containsKey(i)) { |
| 16 | return memo.get(i); |
| 17 | } |
| 18 | |
| 19 | for (int j = i; j < s.length(); j++) { |
| 20 | String prefix = s.substring(i, j + 1); |
| 21 | if (wordSet.contains(prefix) && dp(j + 1, s, wordSet, memo)) { |
| 22 | memo.put(i, true); |
| 23 | return true; |
| 24 | } |
| 25 | } |
| 26 | |
| 27 | memo.put(i, false); |
| 28 | return false; |
| 29 | } |
| 30 | } |
| 1 | #include <string> |
| 2 | #include <vector> |
| 3 | #include <unordered_set> |
| 4 | #include <unordered_map> |
| 5 | |
| 6 | using namespace std; |
| 7 | |
| 8 | class Solution { |
| 9 | public: |
| 10 | bool wordBreak(string s, vector<string>& wordDict) { |
| 11 | unordered_map<int, bool> memo; |
| 12 | unordered_set<string> wordSet(wordDict.begin(), wordDict.end()); |
| 13 | return dp(0, s, wordSet, memo); |
| 14 | } |
| 15 | |
| 16 | private: |
| 17 | bool dp(int i, const string& s, const unordered_set<string>& wordSet, unordered_map<int, bool>& memo) { |
| 18 | if (i == (int)s.size()) { |
| 19 | return true; |
| 20 | } |
| 21 | auto it = memo.find(i); |
| 22 | if (it != memo.end()) { |
| 23 | return it->second; |
| 24 | } |
| 25 | |
| 26 | for (int j = i; j < (int)s.size(); ++j) { |
| 27 | string prefix = s.substr(i, j - i + 1); |
| 28 | if (wordSet.count(prefix) && dp(j + 1, s, wordSet, memo)) { |
| 29 | memo[i] = true; |
| 30 | return true; |
| 31 | } |
| 32 | } |
| 33 | |
| 34 | memo[i] = false; |
| 35 | return false; |
| 36 | } |
| 37 | }; |
| 1 | var wordBreak = function(s, wordDict) { |
| 2 | const memo = new Map(); |
| 3 | const wordSet = new Set(wordDict); |
| 4 | |
| 5 | function dp(i) { |
| 6 | if (i === s.length) { |
| 7 | return true; |
| 8 | } |
| 9 | if (memo.has(i)) { |
| 10 | return memo.get(i); |
| 11 | } |
| 12 | |
| 13 | for (let j = i; j < s.length; j++) { |
| 14 | const prefix = s.substring(i, j + 1); |
| 15 | if (wordSet.has(prefix) && dp(j + 1)) { |
| 16 | memo.set(i, true); |
| 17 | return true; |
| 18 | } |
| 19 | } |
| 20 | |
| 21 | memo.set(i, false); |
| 22 | return false; |
| 23 | } |
| 24 | |
| 25 | return dp(0); |
| 26 | }; |
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
| 6 | def dp(i):
|
| 7 | if i == len(s):
|
| 8 | return True
|
| 9 | if i in memo:
|
| 10 | return memo[i]
|
| 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
|
| 18 | memo[i] = False
|
| 19 | return False
|
Objective
To determine if the substring starting at index i can be segmented by exploring all prefixes and recursively checking suffixes.
Key Insight
The recursion tries every possible prefix starting at i. If a prefix is found in the dictionary, the algorithm recursively checks if the remaining substring can be segmented. Memoization stores the result for index i immediately upon finding a valid segmentation or after exhausting all options, ensuring no repeated work. This approach exploits the problem's optimal substructure and overlapping subproblems.
Interview Quick-Check
Core Logic
The recursive function returns true if any prefix from i to j is in the dictionary and the suffix starting at j+1 can be segmented, capturing the problem's optimal substructure.
State & Boundaries
The base case returns true when the starting index reaches the end of the string, indicating successful segmentation.
Common Pitfalls & Bugs
Forgetting to memoize results leads to exponential time due to repeated recursive calls on the same indices.
Return Final Segmentation Result from Start of String
| 21 | return dp(0) |
Objective
To initiate the recursive segmentation check from the beginning of the string and return the overall result.
Key Insight
Starting the recursion at index 0 triggers the exploration of all valid segmentations of the entire string. The final returned value reflects whether the whole string can be segmented into dictionary words.
Interview Quick-Check
Core Logic
The initial call dp(0) represents the problem of segmenting the entire string, and its result is the answer to the problem.
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.
return TrueCheck if the result for index i is already memoized.
Memoization lookup prevents repeated computation of the same subproblem, ensuring efficient recursion.
word_set = set(wordDict)Convert the word dictionary list into a set for O(1) membership checks.
Using a set enables constant-time prefix lookups, which is critical for efficiently pruning invalid prefixes during recursion.
if i in memo:Return the cached result if available.
Returning memoized results immediately prunes the recursion tree and avoids redundant work.
memo[i] = TrueMemoize true for index i upon finding a valid segmentation.
Storing true for index i ensures future calls immediately know this substring is segmentable, preventing redundant recursion.
memo[i] = FalseMemoize false for index i after exhausting all prefixes without success.
Caching false prevents repeated futile attempts to segment the same substring, pruning the recursion tree.
def dp(i):Define the recursive function dp that checks if s[i:] can be segmented.
Encapsulating the recursive logic in a helper function with index parameter i allows systematic exploration of all suffixes starting at i.
for j in range(i, len(s)):Iterate over possible end indices j for prefixes starting at i.
Exploring all prefixes from i to j ensures all segmentation possibilities are considered.
return TrueReturn true immediately after memoizing a successful segmentation.
Returning early upon success avoids unnecessary further exploration, improving efficiency.
return FalseReturn false indicating no valid segmentation from index i.
Returning false signals that the substring starting at i cannot be segmented into dictionary words.
return dp(0)Start the recursion from index 0 and return the final result.
The initial call represents the entire string, and its return value answers the problem.
prefix = s[i : j + 1]Extract the substring prefix from i to j inclusive.
Checking this prefix against the dictionary determines if it is a valid word to segment.
Test Your Understanding
Why is memoization critical in this recursive solution for Word Break?
Memoization prevents redundant computations by caching whether substrings starting at each index can be segmented, reducing exponential recursion to polynomial time.
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