Skip to main content

139. Word Break

mediumAsked at AMD

Determine if a string can be segmented into words from a dictionary. AMD uses this to test bottom-up DP with substring matching — the same reachability pattern applies to tokenizing instruction streams, parsing ISA assembly strings, and validating opcode sequences in a compiler front-end.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2025-12)— AMD SWE candidates report Word Break appearing in medium rounds, with follow-ups about parsing compiler token streams.
  • Blind (2025-09)— AMD interview threads include Word Break as a standard bottom-up DP medium for SWE and compiler-adjacent roles.

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 lowercase English letters.
  • All the strings of wordDict are unique.

Examples

Example 1

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

Explanation: "leet code" is a valid segmentation.

Example 2

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

Explanation: "apple pen apple" — 'apple' is reused.

Example 3

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

Explanation: No valid segmentation exists.

Approaches

1. Bottom-up DP

dp[i] = true if s[0..i) can be segmented. For each position i, check all j < i where dp[j] is true and s[j..i) is in the dictionary.

Time
O(n^2 * m) where m is avg word length for substring comparison
Space
O(n)
function wordBreak(s, wordDict) {
  const wordSet = new Set(wordDict);
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true; // empty prefix is always valid
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

Tradeoff: O(n^2) in practice (substring slice is O(k) but bounded by max word length). Converting wordDict to a Set first reduces lookup to O(1) average. Clear bottom-up DP structure.

2. BFS with visited set

BFS from index 0. At each position, try all words — if a word matches at the current position, enqueue the end position. Use a visited set to avoid re-processing positions.

Time
O(n^2 * m)
Space
O(n)
function wordBreak(s, wordDict) {
  const wordSet = new Set(wordDict);
  const queue = [0];
  const visited = new Set([0]);
  while (queue.length) {
    const start = queue.shift();
    for (let end = start + 1; end <= s.length; end++) {
      if (visited.has(end)) continue;
      if (wordSet.has(s.slice(start, end))) {
        if (end === s.length) return true;
        visited.add(end);
        queue.push(end);
      }
    }
  }
  return false;
}

Tradeoff: BFS is intuitive for 'reachability' framing but has the same asymptotic complexity. The visited set prevents exponential blowup from revisiting positions.

AMD-specific tips

AMD compiler front-ends tokenize instruction strings and validate opcode sequences against an ISA dictionary — structurally identical to this problem. The bottom-up DP approach maps cleanly to a forward reachability pass: if you can reach position j, and the word from j to i is valid, you can reach position i. Converting wordDict to a Set is mandatory — without it, every lookup is O(|wordDict|) and the total complexity balloons. Mention this optimization explicitly.

Common mistakes

  • Not converting wordDict to a Set — O(n^2 * |wordDict|) instead of O(n^2 * m).
  • Initializing dp[0] = false — the empty string is a valid prefix by definition.
  • Using dp[i-1] instead of dp[j] in the inner loop — you need to try all j < i, not just the immediate predecessor.
  • Using indexOf instead of Set.has for dictionary lookup — linear scan per lookup.

Follow-up questions

An interviewer at AMD may pivot to one of these next:

  • Word Break II (LC 140) — return all valid segmentations (backtracking + memoization).
  • How would you implement this for a streaming token validator in a real-time ISA disassembler?
  • What if words can overlap? (Change the reachability model.)

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 does dp[0] = true?

dp[0] represents the empty prefix. It's always a valid starting point — no characters have been consumed, no segmentation needed. Without dp[0] = true, no dp[i] for i > 0 could ever become true.

How do you handle very long strings efficiently?

Bound the inner loop by the maximum word length in the dictionary — you never need to check substrings longer than the longest word. This reduces the effective inner loop from O(n) to O(max_word_len).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →