Skip to main content

139. Word Break

mediumAsked at Gusto

Determine if a string can be segmented into words from a dictionary. Gusto asks this to test DP thinking — specifically whether you can define the right subproblem and build the table bottom-up without getting tangled in overlapping recursion.

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

Source citations

Public interview reports confirming this problem appears in Gusto loops.

  • Glassdoor (2025-10)— Reported in Gusto mid-level SWE onsite reports as a DP medium used to test string decomposition thinking.
  • Blind (2025-08)— Gusto threads list Word Break as a go-to DP string problem in engineering interviews.

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. The same word in the dictionary may be reused multiple times.

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 in 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: 'applepenapple' = 'apple' + 'pen' + 'apple'. Dictionary words may be 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 j < i: if dp[j] is true and s[j..i-1] is in the wordSet, then dp[i] = true.

Time
O(n³) with string slicing, O(n² · m) with trie
Space
O(n + wordSet 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 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²) outer loops × O(n) for string slicing = O(n³). For n ≤ 300 this is fast enough. Using a Set for O(1) word lookup is important — list lookup would add another factor.

2. Memoised recursion (top-down DP)

Recursively try all dictionary words as the next segment. Memoise by start index to avoid recomputation.

Time
O(n² · m) where m is max word length
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 to the bottom-up approach but uses the call stack. Good for candidates more comfortable with recursion. The memo prevents recomputing the same suffix multiple times.

Gusto-specific tips

Define the subproblem before coding: 'dp[i] = can the first i characters of s be segmented?' Gusto interviewers look for the base case explanation — dp[0] = true because an empty string requires no words. The break statement after finding a valid j is a nice optimisation to mention. Also consider converting wordDict to a Set before the DP loop — not after.

Common mistakes

  • Initialising dp[0] to false — the empty prefix is always valid; dp[0] = true is the required base case.
  • Using wordDict.includes() instead of a Set — O(m) lookup per check, turning the overall complexity to O(n² × m²).
  • Off-by-one: s.slice(j, i) covers indices j through i-1 — verify this matches the dp[j] and dp[i] semantics.
  • In the recursive version, not memoising — leads to exponential time on pathological inputs.

Follow-up questions

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

  • Word Break II (LC 140) — return all possible segmentations as strings.
  • What if some words in the dictionary overlap (one is a prefix of another)?
  • How would you optimise using a Trie to avoid the string slicing cost?

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 is trivially segmentable (using zero words). Without this base case, dp[word.length] would never become true for any first word.

Does reusing words from the dictionary cause issues?

No — the DP naturally handles reuse since the same word can match at multiple (j, i) pairs.

What is the worst-case input?

A string like 'aaa...a' with words like 'a', 'aa', 'aaa' maximises the number of valid segmentations — but the DP still runs in O(n²) since we memoize/tabulate.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →