Skip to main content

139. Word Break

mediumAsked at Glean

Glean asks Word Break because query segmentation — splitting a raw search string like 'enterpriseaichat' into 'enterprise ai chat' — is a real pipeline step in their search engine, and the DP solution maps directly to it.

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

Source citations

Public interview reports confirming this problem appears in Glean loops.

  • Glassdoor (2026-Q1)— Glean interviewers have explicitly connected Word Break to their query-understanding pipeline in candidate feedback.
  • Blind (2025-11)— Ranked among the most Glean-specific interview problems — strong thematic fit with enterprise search query parsing.

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 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: 'apple' + 'pen' + 'apple' — words can 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 the substring s[0..i-1] can be segmented. For each position i, check all substrings s[j..i-1] — if dp[j] is true and s[j..i-1] is in the dictionary, then dp[i] = true.

Time
O(n² * m) where n = s.length, m = avg word length for set lookup
Space
O(n + wordDict size)
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²) inner loops with O(m) per substring comparison. For n=300 and typical word lengths this is very fast. The canonical interview answer.

2. BFS (word-boundary graph traversal)

Model the problem as a graph where each index is a node. Start a BFS from index 0; for each index i, try extending to i+len for every dictionary word. Reach index n to succeed.

Time
O(n * W * m) where W = dictionary size
Space
O(n)
function wordBreak(s, wordDict) {
  const wordSet = new Set(wordDict);
  const visited = new Set();
  const queue = [0];
  while (queue.length > 0) {
    const start = queue.shift();
    if (visited.has(start)) continue;
    visited.add(start);
    for (const word of wordSet) {
      const end = start + word.length;
      if (end <= s.length && s.substring(start, end) === word) {
        if (end === s.length) return true;
        queue.push(end);
      }
    }
  }
  return false;
}

Tradeoff: Equivalent correctness. BFS naturally finds whether the end is reachable. Less common in interviews but worth knowing as an alternative when the interviewer asks for a non-DP approach.

Glean-specific tips

Open with the search-engine angle: 'Word Break is literally query segmentation — a common preprocessing step in enterprise search.' Glean interviewers will light up. For the DP, make the state definition crisp: 'dp[i] is true if the first i characters of s can be segmented.' The connection to Trie lookups is also worth mentioning: in production, the inner loop would query a Trie for efficient prefix matching rather than iterating all j.

Common mistakes

  • Not initializing dp[0] = true — the base case (empty prefix is always valid) is what seeds all subsequent valid segmentations.
  • Using wordDict.includes() instead of a Set — O(W) per lookup vs O(1); causes TLE on large dictionaries.
  • Checking s.substring(i, j) instead of s.substring(j, i) — ensure start < end and the slice direction is correct.
  • Not breaking out of the inner loop when dp[i] is set — wastes time checking further splits after a valid segmentation is found.

Follow-up questions

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

  • Word Break II (LC 140) — return all valid segmentations, not just a boolean.
  • How would you implement this using a Trie for faster prefix lookups?
  • What if the same word can be used at most once? How does the DP change?

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?

dp[i] = true means 's[0..i-1] can be segmented.' The empty prefix (i=0) is trivially valid — you haven't consumed any characters and no segmentation is needed. It acts as the base anchor for all other dp values.

Can you use memoized recursion instead of bottom-up DP?

Yes — define a recursive function canSegment(start) = true if s[start..n-1] can be segmented. Memoize by start index. Top-down is often easier to write but bottom-up is more cache-friendly.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →