139. Word Break
mediumAsked at MicrosoftWord Break is Microsoft's introduction to dynamic programming on strings. The dp[i] = 'is s[0..i] segmentable' framing turns an exponential recursion into a linear-in-n^2 fill. Interviewers want to see you reject memoized DFS as a path to the same answer.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Microsoft loops.
- Glassdoor (2026-Q1)— Microsoft Office/Bing org onsite reports list Word Break as a recurring 30-minute DP medium.
- Blind (2025-12)— Microsoft new-grad and L60 reports include Word Break as a DP introduction question.
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. Note that the same word in the dictionary may be reused multiple times in the segmentation.
Constraints
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s and wordDict[i] consist of only lowercase English letters.All the strings of wordDict are unique.
Examples
Example 1
s = "leetcode", wordDict = ["leet","code"]trueExplanation: Return true because 'leetcode' can be segmented as 'leet code'.
Example 2
s = "applepenapple", wordDict = ["apple","pen"]trueExample 3
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]falseApproaches
1. Bottom-up DP (optimal)
dp[i] = true if s[0..i-1] can be segmented. dp[0] = true. For each i, try every j < i: if dp[j] and s[j..i] is in the dict, set dp[i] = true.
- Time
- O(n^2 * m) worst case where m is avg word length
- Space
- O(n)
function wordBreak(s, wordDict) {
const set = new Set(wordDict);
const dp = new Array(s.length + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && set.has(s.slice(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length];
}Tradeoff: Quadratic in n with a hash lookup per split point. The break-on-true keeps the inner loop short in practice. Microsoft's preferred answer for the clarity of the dp[i] invariant.
2. Top-down memoized DFS
memoize(start): try every word in the dict — if s starts with the word at position start, recurse on start + word.length.
- Time
- O(n^2 * m)
- Space
- O(n) memo + stack
function wordBreak(s, wordDict) {
const memo = new Map();
function solve(start) {
if (start === s.length) return true;
if (memo.has(start)) return memo.get(start);
for (const w of wordDict) {
if (s.startsWith(w, start) && solve(start + w.length)) {
memo.set(start, true);
return true;
}
}
memo.set(start, false);
return false;
}
return solve(0);
}Tradeoff: Equivalent complexity. The bottom-up DP is preferred at Microsoft because the dp[] array is more inspectable and avoids stack-depth worries on large inputs.
3. Naive DFS (rejected)
Try every word at the start, recurse on the suffix. No memoization.
- Time
- Exponential O(2^n)
- Space
- O(n) stack
function wordBreak(s, wordDict) {
if (s === '') return true;
for (const w of wordDict) {
if (s.startsWith(w) && wordBreak(s.slice(w.length), wordDict)) return true;
}
return false;
}Tradeoff: Exponential — same suffix gets re-explored many times. Worth naming and rejecting: 'I'm computing wordBreak('apple') for every path that reaches that suffix — memoize.'
Microsoft-specific tips
Microsoft loves Word Break specifically because the DP state design is non-obvious. Lead with: 'dp[i] is whether s[0..i] can be segmented. Transitions: dp[i] is true if there exists a j < i with dp[j] true AND s[j..i] in the dictionary.' Writing the state definition before the code is what Microsoft graders write down — they're looking for that exact sentence.
Common mistakes
- Using dp[i] to mean 'segmentable up to and INCLUDING i' vs 'up to but NOT including i' — pick one and stick to it.
- Forgetting dp[0] = true (the empty prefix is trivially segmentable).
- s.slice(j, i) inside the inner loop is fine in JS, but in interpreted languages this allocates a substring — be ready to discuss using a trie if asked.
Follow-up questions
An interviewer at Microsoft may pivot to one of these next:
- Word Break II (LC 140) — return ALL valid segmentations.
- Concatenated Words (LC 472) — find words that are concatenations of others.
- What if the dictionary were huge — would you use a trie?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is DP the right approach?
Because the subproblem 'is suffix s[j..] segmentable?' is reused across many parents. Memoization makes the total work polynomial.
What about a trie of the words?
A trie lets you check ALL words starting at position j in a single walk of s. That replaces the inner loop with a single pass and can be faster when the dictionary is large with shared prefixes.
Free learning resources
Curated free links for this problem.