Dynamic Programming · LC #139
Word Break
`dp[i]` tracks whether the prefix `s[0..i-1]` can be formed from dictionary words. For each position, try all splits and check if the suffix is in the word set.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given a string `s` and a list `wordDict`, return `true` if `s` can be segmented into one or more space-separated dictionary words.
Sample I/O
Input: s="leetcode", wordDict=["leet","code"] Output: true Input: s="applepenapple", wordDict=["apple","pen"] Output: true Input: s="catsandog", wordDict=["cats","dog","sand","and","cat"] Output: false
Intuition
How to Think About It
Intuition
Think of each index in `s` as a "checkpoint". If we can reach checkpoint `j` and the substring `s[j..i-1]` is a valid word, we can also reach checkpoint `i`. The problem reduces to reachability in a DAG.
Core Concept
`dp[i]` = can we segment `s[0..i-1]`. Base: `dp[0] = true`. Transition: `dp[i] = true` if any `j < i` satisfies `dp[j] && s[j:i] ∈ wordSet`. Convert wordDict to a set for O(1) lookup.
When to use
String segmentation, tokenization, or any problem where a sequence must be partitioned using a fixed dictionary.
When NOT to use
When you need to enumerate all valid segmentations (use backtracking + memoisation instead). When word count matters rather than existence.
Key Insights
What to Know Cold
- Converting wordDict to a HashSet reduces word lookup from O(k) to O(1) amortised.
- dp[0] = true is the "empty prefix" base case - essential for the first word to be recognised.
- The inner loop split point j can be pruned: only try j values where dp[j] is already true.
- For large dictionaries, iterate over words instead of split points to reduce inner loop iterations.
- Trie + DP can further reduce time to O(n · L_max) where L_max is the longest dictionary word.
1 example
Worked Examples
Segment "leetcode" into dictionary words
wordDict = ["leet","code"]. Determine if "leetcode" is fully segmentable.
DP with HashSet: propagate reachability across split points.
Output: true
Appears at Amazon, Google, and Meta. Tests both DP formulation skill and the habit of converting lists to sets for fast lookups - a common missed optimisation.