139. Word Break

Q: Why does dp[0] = true?

It represents the empty prefix — a valid starting state. Without it, no word starting at index 0 would ever be recognized.

Q: Why break after finding a valid j?

Once dp[i] = true, we don't need to find all valid j values — we only need to know if at least one exists. Breaking avoids redundant work.

Q: How does the trie optimization help?

Instead of generating substrings from each position i, a trie walk from dp[j]-true positions extends one character at a time, naturally constraining the search to existing dictionary prefixes.

mediumAsked at DRW

DRW surfaces Word Break to test DP on string segmentation — a pattern that maps to parsing FIX tag-value sequences and tokenizing structured market messages where the dictionary of valid tokens is known in advance.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in DRW loops.

Glassdoor (2025-Q4)— DRW SWE candidates report string DP problems including Word Break in medium-difficulty onsite coding rounds.
Blind (2025-10)— DRW interview threads note Word Break is used to assess bottom-up DP discipline and trie optimization awareness.

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". Reuse allowed.

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 index i, check all j < i where dp[j] is true and s[j..i-1] is in the dictionary.

Time: O(n² × m) where m = average 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.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

Tradeoff: O(n²) substring iterations plus O(m) for each substring lookup. For n=300 and m=20 this is at most 300×300×20 = 1.8M operations — fast enough. The Set lookup avoids linear dictionary scans.

2. DP optimized with max word length

For each position i, only check substrings of length up to the maximum dictionary word length. Reduces the inner loop iterations significantly for short dictionaries.

Time: O(n × maxLen × m)
Space: O(n)

function wordBreak(s, wordDict) {
  const wordSet = new Set(wordDict);
  const maxLen = Math.max(...wordDict.map(w => w.length));
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let len = 1; len <= Math.min(i, maxLen); len++) {
      if (dp[i - len] && wordSet.has(s.substring(i - len, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

Tradeoff: Reduces the inner loop to O(maxLen) instead of O(n). For short dictionaries (maxLen ≪ n), significant practical speedup. DRW appreciates this optimization.

DRW-specific tips

After the DP solution, DRW will ask: 'How would you build a trie from the dictionary and use it to drive the DP?' The trie allows you to extend from each valid dp[i] position, walking the trie character by character — O(n × maxLen) time with O(total dictionary characters) space. They may also ask: 'If the dictionary has 10,000 words and the string is 10,000 characters long, what is the time complexity?' — that is when the trie optimization becomes critical over the naive Set-based DP.

Common mistakes

Not initializing dp[0] = true — the empty prefix is always a valid segmentation base case.
Using s.slice() instead of s.substring() — both work, but substring is slightly clearer for index-based slicing.
Not using a Set for O(1) dictionary lookups — linear array scan makes the algorithm O(n² × |wordDict|).
Forgetting that words can be reused — the DP checks all prior positions, allowing repeated use of the same word.

Follow-up questions

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

Word Break II (LC 140) — return all possible segmentation sentences.
How would you implement this using a trie for O(n × maxLen) time?
How does this problem relate to tokenizing structured binary protocol messages in a trading system?

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?

It represents the empty prefix — a valid starting state. Without it, no word starting at index 0 would ever be recognized.

Why break after finding a valid j?

Once dp[i] = true, we don't need to find all valid j values — we only need to know if at least one exists. Breaking avoids redundant work.

How does the trie optimization help?

Instead of generating substrings from each position i, a trie walk from dp[j]-true positions extends one character at a time, naturally constraining the search to existing dictionary prefixes.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →