Skip to main content

139. Word Break

mediumAsked at eBay

eBay's search team segments raw query strings into recognizable product keywords — 'iPhonecase' into 'iPhone' and 'case'. Word Break is the dynamic programming core of this segmentation problem. eBay interviewers use it to test bottom-up DP intuition and hash-set lookup optimization for the dictionary.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2025-12)— Cited as a common eBay medium DP problem in the second or third onsite round, often framed around search query parsing.
  • Blind (2025-09)— eBay SWE threads recommend Word Break as a high-probability DP problem for mid-level 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. 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' 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 j < i: if dp[j] is true and s[j..i-1] is in the dictionary, then dp[i] = true.

Time
O(n² * m) where m is avg word length for substring comparison
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; // no need to check further j values
      }
    }
  }
  return dp[n];
}

Tradeoff: O(n²) with Set lookups. The Set avoids linear dictionary scanning. Breaking early when dp[i] is set is a small optimization. This is the canonical DP solution eBay expects.

2. Memoized DFS

Try every word in the dictionary as the prefix of the remaining string. Recurse on the suffix. Memoize on the start index to avoid recomputing.

Time
O(n² * m)
Space
O(n)
function wordBreak(s, wordDict) {
  const wordSet = new Set(wordDict);
  const memo = new Map();
  function dfs(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)) && dfs(end)) {
        memo.set(start, true);
        return true;
      }
    }
    memo.set(start, false);
    return false;
  }
  return dfs(0);
}

Tradeoff: Same asymptotic complexity as bottom-up DP. Useful if you find top-down easier to reason about. eBay interviewers accept either — mention both and let them guide the preference.

eBay-specific tips

State the DP meaning before coding: 'dp[i] means s[0..i-1] can be validly segmented.' eBay interviewers appreciate the Set optimization: 'I put wordDict in a Set for O(1) lookups instead of O(dict.length) linear scan per check.' The follow-up 'return all valid segmentations' (LC 140) is common — that requires backtracking and memoization of the path, not just a boolean.

Common mistakes

  • Forgetting dp[0] = true — the empty prefix is always a valid segmentation base case.
  • Using wordDict.includes(s.slice(j, i)) instead of a Set — O(dict) per lookup, degrading to O(n² * dict) overall.
  • Off-by-one on dp array size — dp needs n+1 elements (dp[0] through dp[n]).
  • Not breaking early when dp[i] becomes true — minor inefficiency but shows lack of optimization awareness.

Follow-up questions

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

  • Word Break II (LC 140) — return all valid segmentation strings, not just a boolean; requires backtracking.
  • How would you handle a very large dictionary (millions of words) efficiently? (Trie prefix structure)
  • How would you adapt this if words in the dictionary had weights and you wanted the maximum-weight segmentation?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

What does dp[0] = true represent?

It means the empty prefix (s[0..−1]) is trivially segmented. Without this base case, dp[i] could never be set to true — every check dp[j] would start from a false initial state.

Why is a Set preferred over an array for the dictionary?

Set.has() is O(1) on average vs. Array.includes() which is O(dict.length). With a 1000-word dictionary and 300-character string, the savings are significant.

Can this be solved with BFS?

Yes — treat each index as a node. BFS from 0, enqueue all positions reachable by a valid word prefix. This is conceptually identical to the bottom-up DP but expressed as graph traversal.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →