Word Break
Asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian, Salesforce
Problem
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Netflix | Medium | View all Netflix questions → |
| Uber | Medium | View all Uber questions → |
| Atlassian | Medium | View all Atlassian questions → |
| Salesforce | Medium | View all Salesforce questions → |
How to Think About It
dp[i] = true if s[0:i] can be segmented into dictionary words. Base case: dp[0] = true (empty string is always segmentable).
For each position i, try every possible last word: if dp[j] is true (s[0:j] is segmentable) AND s[j:i] is in the dictionary, then dp[i] = true.
Why it works: you're building solutions from left to right. If you can reach position j and there's a word from j to i, you can reach i.
Optimization: limit j to i - maxWordLength. No point checking positions further back than the longest dictionary word.
Trie optimization: instead of checking s[j:i] in a hash set, traverse a trie as you scan s from j to i. Stops early on mismatch.
Visual walkthrough for s="leetcode", wordDict=["leet","code"]:
dp[0]=T, dp[1..8]=F
i=4: j=0, dp[0]=T and s[0:4]="leet" in dict → dp[4]=T
i=8: j=4, dp[4]=T and s[4:8]="code" in dict → dp[8]=T
Result: true
Edge cases: empty string (true), single character in dict (check if it matches), overlapping words.
Optimal Approach
Step 1: Create dp array of size len(s)+1, all false. dp[0] = true.
Step 2: Convert wordDict to a set for O(1) lookup. Find max word length.
Step 3: For i from 1 to len(s):
For j from 0 to i:
If dp[j] and s[j:i] in word_set:
dp[i] = true
break
Step 4: Return dp[len(s)].
Time: O(n² × k) where k is max word length. Space: O(n).
What Trips People Up in Real Interviews
Confusing "word break" with "word search." This problem is about segmenting a string, not searching a grid.
Not using a set for dictionary lookups. Checking if a substring is in the dictionary is O(k) with a list but O(1) with a set.
Forgetting that dp[0] = true. The empty string is always segmentable.
Not optimizing the inner loop. No need to check j values further back than the longest dictionary word.
Not breaking out of the inner loop early. Once dp[i] is set to true for any j, you've found a valid segmentation — no need to check other split points. Breaking early avoids unnecessary work.
Solution Code
def wordBreak(s, wordDict):
word_set = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]Frequently Asked Questions
What is the Word Break problem?
Given a string s and a dictionary of strings wordDict, return `true` if s can be segmented into a space-separated sequence of one or more dictionary words.
How do you solve Word Break?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Word Break?
Word Break is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian, Salesforce. It is a medium difficulty problem.
What are common mistakes on Word Break?
- Confusing "word break" with "word search." This problem is about segmenting a string, not searching a grid.
- Not using a set for dictionary lookups. Checking if a substring is in the dictionary is `O(k)` with a list but `O(1)` with a set.
- Forgetting that `dp[0]` = `true`. The empty string is always segmentable.
- Not optimizing the inner loop. No need to check j values further back than the longest dictionary word.
- Not breaking out of the inner loop early. Once `dp[i]` is set to `true` for any j, you've found a valid segmentation — no need to check other split points. Breaking early avoids unnecessary work.