Skip to main content

139. Word Break

mediumAsked at Anduril

Determine whether a string can be segmented into words from a given dictionary. Anduril uses this DP problem to test whether you can formulate a 1D DP recurrence, recognize subproblem overlap, and choose appropriate memoization — skills that map to parsing structured command protocols with a fixed grammar.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

  • Glassdoor (2025-11)— Cited in Anduril SWE onsite threads as a DP-string medium in technical rounds.
  • Blind (2025-08)— Anduril candidates describe Word Break as appearing in algorithm-heavy rounds for senior and mid-level SWE 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 only lowercase English letters.
  • All the strings of wordDict are unique.

Examples

Example 1

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

Explanation: 'leetcode' can be split as 'leet code'.

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-1] can be segmented. For each position i, check all substrings s[j..i-1] for j in [0,i) and see if dp[j] is true and s[j..i-1] is in the dictionary.

Time
O(n^2 * k) where k is average word length for substring comparison
Space
O(n + dictionary size)
function wordBreak(s, wordDict) {
  const wordSet = new Set(wordDict);
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true; // empty string 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;
      }
    }
  }
  return dp[n];
}

Tradeoff: Clean O(n^2) DP. Converting wordDict to a Set gives O(1) average lookup. The slice operation is O(k) per check — mention this. This is the standard expected answer.

2. Top-down DP with memoization

Recursively try to match prefixes of s against the dictionary. Memoize the result for each start index.

Time
O(n^2 * k)
Space
O(n)
function wordBreak(s, wordDict) {
  const wordSet = new Set(wordDict);
  const memo = new Map();
  function canBreak(start) {
    if (start === s.length) return true;
    if (memo.has(start)) return memo.get(start);
    for (let end = start + 1; end <= s.length; end++) {
      if (wordSet.has(s.slice(start, end)) && canBreak(end)) {
        memo.set(start, true);
        return true;
      }
    }
    memo.set(start, false);
    return false;
  }
  return canBreak(0);
}

Tradeoff: Equivalent complexity. Top-down can exit early as soon as a valid path is found. Some find the recursive structure easier to reason about. Same worst-case as bottom-up.

Anduril-specific tips

State the DP recurrence clearly before coding: 'dp[i] is true if any prefix dp[j] is true and the substring s[j..i-1] is in the dictionary.' Anduril values engineers who can articulate the subproblem definition before writing code. Use a Set for dictionary lookup to avoid O(n) linear scans per check. Mention the optimization of bounding the inner loop by the maximum word length in the dictionary — this reduces the O(n^2) inner loop to O(n * maxWordLen).

Common mistakes

  • Initializing dp[0] to false — the empty string is always segmentable (zero words used); dp[0] = true is the base case.
  • Using wordDict.includes() instead of a Set — O(m) per lookup degrades total to O(n^2 * m).
  • Forgetting to break early after setting dp[i] = true — the inner loop can be exited since we only need one valid j.
  • Off-by-one in the slice bounds — s.slice(j, i) gives s[j..i-1], which is the correct substring for dp[i].

Follow-up questions

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

  • Word Break II (LC 140) — return all possible segmentations, not just whether one exists.
  • How do you bound the inner loop to improve constant factors?
  • How would you solve this for a very large dictionary using a trie instead of a hash 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, which requires zero words and is trivially valid. Without it, no dp[i] where s[0..i-1] is a single word would ever be set to true.

Can the same word be used multiple times?

Yes — the problem states this explicitly. The DP structure handles it naturally since j can be set to any previously-true position.

Is a trie faster than a set in practice?

For large dictionaries with many common prefixes, a trie reduces redundant substring comparisons. For this problem's constraints (dictionary ≤ 1000 words, word length ≤ 20), a set is fast enough.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →