Skip to main content

139. Word Break

mediumAsked at Google

Given a string and a dictionary, return true if the string can be segmented into dictionary words. Google asks this to test whether you reach for DP and can articulate why a hash set of words + a boolean DP table gives O(n^2) instead of the exponential backtracking blowup.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L4 onsite reports cite this as the DP round.
  • Blind (2025-10)— Multiple Google interview reports list Word Break as a 40-minute medium.

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: Return true because "leetcode" can be segmented as "leet code".

Example 2

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

Example 3

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

Approaches

1. Backtracking

Try every prefix that's a word, recurse on the remainder.

Time
O(2^n)
Space
O(n)
function wordBreakBacktrack(s, wordDict) {
  const set = new Set(wordDict);
  function solve(start) {
    if (start === s.length) return true;
    for (let end = start + 1; end <= s.length; end++) {
      if (set.has(s.slice(start, end)) && solve(end)) return true;
    }
    return false;
  }
  return solve(0);
}

Tradeoff: Exponential in the worst case (a string like 'aaaa...a' with dict ['a','aa','aaa']). The repeated work motivates memoization.

2. DP (optimal)

dp[i] = true if s[0..i] can be segmented. dp[i] = OR over j < i of (dp[j] AND s[j..i] is in dict).

Time
O(n^2 * m)
Space
O(n)
function wordBreak(s, wordDict) {
  const set = new Set(wordDict);
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && set.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

Tradeoff: Bottom-up DP. The 'm' factor is the substring slice + hash lookup. Constant-factor optimization: cap the inner loop at the max word length in wordDict.

Google-specific tips

Google interviewers want you to articulate the subproblem clearly: dp[i] = 'can the prefix of length i be segmented?' Talk about why the backtracking is exponential (overlapping subproblems on the suffix) before writing the DP. The bonus optimization Google likes: cap the inner loop length at the longest word in wordDict.

Common mistakes

  • Forgetting that the same word can be used multiple times.
  • Off-by-one with dp[0] = true (empty prefix is trivially segmentable).
  • Not breaking out of the inner loop once dp[i] becomes true — wastes constant factors.

Follow-up questions

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

  • Word Break II (LC 140): return all valid segmentations.
  • What if the dictionary is too large to fit in memory? (Trie + streaming.)
  • Could you do it with 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 DP and not BFS?

BFS over positions also works (treat each segmentable prefix as a node), same asymptotic complexity. DP is more idiomatic because the substructure is naturally indexed by prefix length.

What's the trick interviewers want to see?

Capping the inner loop at the longest dictionary word — it doesn't change the asymptotic bound but is what separates 'good' from 'great' candidates.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →