139. Word Break

Q: Why is dp[0] = true?

It represents the empty prefix — before consuming any character. It serves as the base case that allows the first word to be found.

Q: Does word reuse change the algorithm?

No — because the DP checks all possible split points, each word can be matched multiple times naturally.

Q: What is the time complexity if dictionary words have a maximum length L?

You can prune the inner loop to only consider substrings of length up to L: for j from max(0, i-L) to i. This reduces the inner loop and improves practical performance.

mediumAsked at Broadcom

Determine if a string can be segmented into valid dictionary words. Broadcom asks this to test DP on strings — the same segmentation logic underlies pattern-matching in network packet payload inspection and protocol-field tokenisation in deep-packet inspection engines.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

Glassdoor (2025-11)— Reported in Broadcom SWE onsite reports as a string DP problem in infrastructure software rounds.
Blind (2025-09)— Broadcom threads list Word Break as a medium DP problem that pairs naturally with Coin Change.

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 segmented as "leet code".

Example 2

Input

s = "applepenapple", wordDict = ["apple","pen"]

Output

true

Explanation: "apple pen apple" — 'apple' 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] where dp[j] is true. If the substring is in the word set, set dp[i] = true.

Time: O(n² * m) where m is average word length for substring match
Space: O(n + dict 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 prefix is always valid
  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: O(n²) DP transitions. Using a Set for O(1) word lookup is critical. The break statement short-circuits once dp[i] is set. Clear and easy to verify correctness.

2. Memoised recursion (top-down)

Recursive function wordBreak(start) checks if s[start..n] can be segmented. Memoise results by start index to avoid recomputation.

Time: O(n² * m)
Space: O(n)

function wordBreak(s, wordDict) {
  const wordSet = new Set(wordDict);
  const memo = new Map();
  function dp(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)) && dp(end)) {
        memo.set(start, true);
        return true;
      }
    }
    memo.set(start, false);
    return false;
  }
  return dp(0);
}

Tradeoff: Same asymptotic complexity. Top-down is often easier to reason about during an interview because it mirrors the natural recursive definition.

Broadcom-specific tips

At Broadcom, state the DP transition clearly before coding: 'dp[i] is true if there exists a split point j < i where dp[j] is true and s[j..i-1] is a dictionary word.' Use a Set (not an array) for the dictionary to ensure O(1) word lookup. Broadcom follow-ups often ask about Word Break II (returning all segmentations) — mention that returning paths requires backtracking or storing the valid split points.

Common mistakes

Using an array instead of a Set for dictionary lookups — .includes() is O(m) per lookup, significantly worsening performance.
Initialising dp[0] = false — the empty prefix must be true as the base case.
Not breaking early after setting dp[i] = true — causes unnecessary extra checks.
Off-by-one in slice indices — s.slice(j, i) gives s[j] through s[i-1], which is correct for dp[i].

Follow-up questions

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

Word Break II (LC 140) — return all valid segmentations (backtracking with memoisation).
Minimum number of words to segment the string.
How would you handle a dictionary that is too large to fit in memory (trie-based streaming lookup)?

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 — before consuming any character. It serves as the base case that allows the first word to be found.

Does word reuse change the algorithm?

No — because the DP checks all possible split points, each word can be matched multiple times naturally.

What is the time complexity if dictionary words have a maximum length L?

You can prune the inner loop to only consider substrings of length up to L: for j from max(0, i-L) to i. This reduces the inner loop and improves practical performance.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →