Word Break
Problem Statement
Given a string s and a dictionary wordDict containing unique words, return true if s can be segmented into a space-separated sequence of one or more dictionary words. The same dictionary word may be reused multiple times.
Input
A string s and a list of dictionary words wordDict.
Output
A boolean: true if the full string can be segmented into dictionary words, otherwise false.
Constraints
- •
1 <= s.length <= 300 - •
1 <= wordDict.length <= 1000 - •
1 <= wordDict[i].length <= 20 - •
**s** and **wordDict[i]** consist only of lowercase English letters. - •
All strings in **wordDict** are unique.
Examples
Example 1
s = "leetcode", wordDict = ["leet", "code"]
trueExample 2
s = "applepenapple", wordDict = ["apple", "pen"]
trueExample 3
s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
falseLearning Objectives
- Model segmentation as a prefix decision: choose the last word ending at position **i**.
- Use **dp[i]** to record whether the first **i** characters are segmentable.
- Use a **HashSet** so dictionary membership checks are fast enough inside the DP loops.
- Recognise an OR recurrence over all valid cut positions **j < i**.
Intuition
Think about the last word in a valid segmentation. If the string prefix ending at index i is segmentable, then there must be some earlier cut j where the prefix before j was already segmentable and the slice from j to i is one dictionary word.
That turns the problem into a yes or no question for every prefix length. We do not need to remember the actual sequence of words for this version. We only need to know whether a prefix can be completed. Once dp[j] is true, any dictionary word starting at j can extend a valid segmentation to a later prefix.
The empty prefix matters. Setting dp[0] = true means a word that starts at the beginning of s can be accepted without needing a previous real word.
Common mistakes
- ×Forgetting **dp[0] = true**, which prevents words that start at index 0 from ever being accepted.
- ×Checking dictionary membership with a list scan instead of a **HashSet**, making the nested loops unnecessarily slow.
- ×Treating a failed cut as proof that **dp[i]** is false; you must try every possible cut **j < i** until one works.
- ×Confusing substring boundaries: in Java, **substring(j, i)** includes **j** and excludes **i**.
- ×Assuming each dictionary word can be used once; the problem allows unlimited reuse.
State Definition
Let dp[i] be true when the prefix s[0..i), the first i characters of s, can be segmented entirely into dictionary words. The answer is dp[n], where n = s.length().
State Transition
For each ending position i, try every earlier cut j < i. The cut is valid when the prefix before the cut is already segmentable and the new piece is in the dictionary:
dp[i] = OR over j < i of (dp[j] AND dict.contains(s.substring(j, i)))
The base case is dp[0] = true because the empty prefix is segmentable by choosing no words. All other states start as false until a valid cut proves them reachable.
Solutions
Solution: Bottom-up prefix DP with HashSet
Use this in interviews as the standard solution: it directly expresses the cut decision, avoids exponential recursion, and is easy to optimise with a maximum word length bound.
Store the dictionary in a HashSet. Sweep the end index from left to right, and for each end index test possible starts of the last word. If dp[start] is true and the slice s[start..end) is a dictionary word, then dp[end] becomes true and we can stop checking that end index.
Step-by-step
- Convert wordDict into a HashSet and record the maximum word length so impossible long slices are skipped.
- Create a boolean table of length n + 1 and set dp[0] = true.
- For each end from 1 through n, try start positions that could form a dictionary word ending at end.
- When dp[start] is true and s.substring(start, end) is in the set, mark dp[end] = true and break the inner loop.
- Return dp[n] after every prefix has been considered.
O(n · L²)
O(n + D)
**L** is the maximum dictionary word length and **D** is the total dictionary storage. Java substring creation costs up to O(L) per candidate.
Java implementation
Dry Run
Sample input
s = leetcode, wordDict = [leet, code]. Track whether each prefix length can be segmented.
| i | prefix | valid cut | dp[i] | reason |
|---|---|---|---|---|
| 0 | empty | base | true | The empty prefix starts the recurrence. |
| 1 | l | none | false | No dictionary word completes a segmentable prefix. |
| 2 | le | none | false | The slice le is not in the dictionary. |
| 3 | lee | none | false | The slice lee is not in the dictionary. |
| 4 | leet | 0 | leet | true | **dp[0]** is true and leet is a dictionary word. |
| 5 | leetc | none | false | The remaining suffix c is not a word. |
| 6 | leetco | none | false | No cut creates a known word after a true prefix. |
| 7 | leetcod | none | false | cod is not in the dictionary. |
| 8 | leetcode | 4 | code | true | **dp[4]** is true and code is a dictionary word. |
The table reaches dp[8] = true because the valid cut at 4 separates leet from code. Therefore the full string is segmentable.
Complexity Analysis
The core DP checks possible last-word cuts for each prefix. The maximum-word-length bound keeps the loop practical for the given constraints while preserving the same recurrence.
Bottom-up prefix DP with HashSet
O(n · L²)
O(n + D)
**L** is the maximum dictionary word length and **D** is the total dictionary storage. Java substring creation costs up to O(L) per candidate.
Interview Tips
Lead with the prefix state, then derive the recurrence from the last word of the segmentation. Mention dp[0] = true before writing loops; that base case is the most common source of bugs. If asked to return all segmentations, explain that the boolean table becomes a pruning guide and the output itself may be exponential.
Likely follow-ups
- Return one valid segmentation instead of only **true** or **false**.
- Return all valid segmentations, as in Word Break II.
- How would the solution change if dictionary membership supported wildcard characters?
- Can you reduce substring allocation costs by grouping words by length or using a trie?
Similar Problems
Key Takeaways
- Decision DP often asks whether a prefix can be formed by choosing one valid final piece.
- **dp[0] = true** represents the empty prefix and allows the first word to start at index 0.
- A **HashSet** turns dictionary validation into a fast predicate inside the cut loop.
- Once one cut proves **dp[i]** true, the remaining cuts for that **i** are unnecessary.