Word Break Problem: How Do You Solve It?
Learn to solve the word break problem with dynamic programming, hash-set dictionary lookups, and the Word Break II variant.
Expected Interview Answer
The word break problem — deciding whether a string can be segmented into a sequence of words from a given dictionary — is solved with dynamic programming where dp[i] is true if the substring ending at index i can be fully segmented, computed by checking every earlier split point j where dp[j] is true and s[j:i] is in the dictionary, in O(n^2) time using a hash set for O(1) dictionary lookups.
Define dp[i] as true when s[0:i] can be broken into dictionary words; dp[0] is true by definition, representing the empty prefix. For each end position i, scan every possible split point j from 0 to i, and if dp[j] is true and the substring s[j:i] exists in the dictionary set, then dp[i] is true and you can stop scanning further j values for that i. The dictionary must be stored as a hash set, not a list, so each substring membership check is O(1) instead of O(k) per word, keeping the overall complexity O(n^2) rather than O(n^2 * k). A related harder variant, "word break II", asks for all possible segmentations rather than just a yes/no answer, which typically needs memoized backtracking since the output itself can be exponential in size.
- O(n^2) time with a hash set for O(1) dictionary lookups
- O(n) space for the dp boolean array
- dp[0] = true anchors the recurrence cleanly
- Extends to Word Break II via memoized backtracking for all segmentations
AI Mentor Explanation
Determining whether a full day’s over count can be broken exactly into legal spell lengths a bowler is allowed to bowl is like the word break problem. You track, for every over count from zero up to the day’s total, whether that many overs can be built entirely from valid spell lengths, starting from the fact that zero overs bowled is trivially valid. For each candidate over count, you check every earlier valid over count and see if the gap between them matches a legal spell length, marking the current count valid the moment one such gap works. This is exactly how dp[i] being true, built from dp[j] being true plus a valid "word" (spell) from j to i, proves the whole day’s overs can be legally partitioned.
Step-by-Step Explanation
Step 1
Build a dictionary hash set
Convert the word list into a set for O(1) membership checks instead of O(k) list scans.
Step 2
Define dp[i]
dp[i] = true if s[0:i] can be fully segmented into dictionary words; dp[0] = true as the base case.
Step 3
Fill dp left to right
For each i, check every j < i where dp[j] is true and s[j:i] is in the dictionary; if found, set dp[i] = true and stop scanning.
Step 4
Return dp[n]
The final entry dp[len(s)] tells whether the entire string can be segmented.
What Interviewer Expects
- Define the dp[i] state precisely (segmentable prefix of length i)
- Use a hash set for the dictionary, not a list, to keep lookups O(1)
- Correctly seed dp[0] = true and explain why
- Recognize Word Break II (returning all segmentations) needs memoized backtracking, not just the boolean DP
Common Mistakes
- Using a list for dictionary lookups, silently making the solution O(n^2 * k) or worse
- Forgetting dp[0] = true, which breaks the recurrence for every subsequent index
- Not breaking out of the inner loop once dp[i] is found true, wasting time (a minor inefficiency, not correctness)
- Confusing Word Break (boolean feasibility) with Word Break II (enumerate all valid segmentations)
Best Answer (HR Friendly)
“Word break asks whether a string can be split into a sequence of words that all exist in a given dictionary. I solve it with dynamic programming by tracking, for every prefix of the string, whether that prefix is fully segmentable — building each answer from a shorter segmentable prefix plus one more dictionary word — and using a hash set for the dictionary so each word check is instant.”
Code Example
def word_break(s: str, word_dict: list[str]) -> bool:
words = set(word_dict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[n]
# word_break("leetcode", ["leet", "code"]) -> TrueFollow-up Questions
- How would you solve Word Break II, returning every valid segmentation?
- How would you reduce redundant substring checks using a trie of dictionary words?
- What is the worst-case time and space complexity of your solution, and where does it come from?
- How would you handle a very large dictionary — does the hash set choice still hold up?
MCQ Practice
1. Why should the dictionary be stored as a hash set rather than a list?
A hash set gives O(1) average-time membership testing, which keeps the overall DP at O(n^2) instead of O(n^2 * k).
2. What does dp[i] represent in the word break DP formulation?
dp[i] is a boolean indicating whether the prefix of length i can be built entirely from dictionary words.
3. What is the key difference between Word Break and Word Break II?
Word Break asks a yes/no feasibility question; Word Break II must enumerate every valid way to segment the string.
Flash Cards
What is the dp[i] state in the word break problem? — True if the prefix s[0:i] can be fully segmented into dictionary words.
What is the base case for word break DP? — dp[0] = true, representing the trivially segmentable empty prefix.
What is the time complexity of the standard word break DP? — O(n^2) with an O(1) hash-set dictionary lookup at each step.
How does Word Break II differ from Word Break? — It returns all valid segmentations instead of just a boolean, typically via memoized backtracking.