Word Break
Understand the problem
Given a string s and a list of words wordDict, can s be segmented into a sequence of words from wordDict? A word may be used multiple times.
Example:
ts
s = "leetcode", wordDict = ["leet","code"]
output = true // "leet" + "code"
s = "applepenapple", wordDict = ["apple","pen"]
output = true // "apple" + "pen" + "apple"
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
output = false // no valid segmentationThe trap: greedily cutting at the first matching word is wrong.
- For "catsandog", you can cut "cat" and then "sand", which leaves "og" stuck — but you can't conclude false yet, because other cuts haven't been tried ("cats" + "and"...).
- You have to consider every way to cut without recomputing overlapping work — that is the job of dynamic programming.
Basic approach
O(2ⁿ) time, O(n) space (call stack) — each position can split or notts
// Plain recursion without memoization — try every split
function wordBreakNaive(s: string, wordDict: string[]): boolean {
const wordSet = new Set(wordDict)
function dfs(start: number): boolean {
if (start === s.length) return true
for (let end = start + 1; end <= s.length; end++) {
const word = s.slice(start, end)
if (wordSet.has(word) && dfs(end)) return true
}
return false
}
return dfs(0)
}Why this approach is slow:
It recomputes the same subproblem from many different branches.
Adding memoization (caching the result of dfs(i)) brings it down to O(n²×m) — equivalent to bottom-up DP.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.