Skip to main content

139. Word Break

mediumAsked at Citadel

Word Break is a DP problem about partitioning — given a string and a dictionary, can the string be segmented into valid words? At Citadel, analogous problems appear in pattern recognition on order strings and in tokenizing structured text streams. The interview tests DP state definition and whether you avoid re-checking overlapping subproblems.

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

Source citations

Public interview reports confirming this problem appears in Citadel loops.

  • Glassdoor (2025-11)— Citadel SWE candidates report DP string partitioning problems as a common on-site category, with Word Break cited specifically.
  • Blind (2025-09)— Citadel SWE threads identify Word Break as a test of DP state design — interviewers push candidates to articulate the subproblem clearly.

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: 'leetcode' = 'leet' + 'code'.

Example 2

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

Explanation: 'apple' + 'pen' + 'apple'. The word 'apple' is reused.

Example 3

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

Explanation: Cannot partition completely.

Approaches

1. Bottom-up DP

dp[i] = true if s[0..i-1] can be segmented. For each i, check all j < i: if dp[j] is true and s[j..i-1] is in the dictionary, set dp[i] = true.

Time
O(n² * m) where n = s.length, m = avg word length for substring comparison
Space
O(n + dict size)
function wordBreak(s, wordDict) {
  const wordSet = new Set(wordDict); // O(1) lookup
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true; // empty prefix is always segmentable

  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.slice(j, i))) {
        dp[i] = true;
        break; // no need to check further j values
      }
    }
  }
  return dp[n];
}

Tradeoff: O(n²) DP transitions, each with O(m) string slice and Set lookup. For n = 300 and max word length 20, very fast in practice. The break after finding dp[i] = true is an important optimization.

2. BFS / memoized recursion

BFS from index 0. At each position, try all dictionary words as the next segment. Mark visited positions to avoid re-exploring. Equivalent to DP but expressed differently.

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

Tradeoff: BFS formulation is intuitive for those who think graph-first. The visited set is crucial — without it, the same starting position is explored O(n) times, making the algorithm exponential. Equivalent to DP in complexity.

Citadel-specific tips

State the DP subproblem before coding: 'dp[i] = can s[0..i-1] be segmented. Transition: dp[i] = OR over all j where dp[j] is true AND s[j..i-1] is in the dictionary.' Citadel interviewers will ask you to optimize: 'Instead of checking all j < i, can you only check up to maxWordLength characters back?' Yes — this reduces the inner loop from O(n) to O(maxWordLen) = O(20) per position, giving O(n * maxLen) overall. Always mention this optimization unprompted.

Common mistakes

  • Forgetting dp[0] = true — the base case is that the empty string is always segmentable.
  • Not converting wordDict to a Set — O(k) list lookup inside a nested loop creates O(n² * k) complexity.
  • Using s.substring(j, i) or s.slice(j, i) inconsistently — both work in JS, but be consistent and explicit about the half-open interval.
  • In the BFS approach, not tracking visited positions — leads to exponential re-exploration.

Follow-up questions

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

  • Word Break II (LC 140) — return all valid segmentations as strings.
  • How does the complexity change if you iterate only up to maxWordLength characters back?
  • How would you solve this with a Trie instead of a Set?

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

It represents the empty prefix — an empty string requires no words to partition, so it's trivially true. Without this base case, no segment of s would ever be reachable.

What is the time complexity when the inner loop is limited to maxWordLen?

O(n * maxWordLen * m) where m is the average word length for hash computation. If maxWordLen = 20, this is effectively O(20n) = O(n) in practice.

Can this be solved with a Trie?

Yes — build a Trie from wordDict. At each DP position, traverse the Trie for s[i..] and record all valid end positions in O(maxWordLen) per start position, achieving the same O(n * maxWordLen) bound.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →