Skip to main content

139. Word Break

mediumAsked at Microsoft

Word 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 Alex Chen, 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 <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.

Examples

Example 1

Input
s = "leetcode", wordDict = ["leet","code"]
Output
true

Explanation: Return true because 'leetcode' can be segmented as 'leet code'.

Example 2

Input
s = "applepenapple", wordDict = ["apple","pen"]
Output
true

Example 3

Input
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output
false

Approaches

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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Word Break and other Microsoft interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →