Skip to main content

78. Word Break

mediumAsked at Snowflake

Decide whether a string can be segmented into a sequence of dictionary words. Snowflake asks this for 1D DP with set lookup — relevant to query-rewrite where you match identifier strings against catalog tables.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this in onsites.
  • LeetCode Discuss (2025-11)— Reported at Snowflake SDE-I screens.

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.

Examples

Example 1

Input
s = "leetcode", wordDict = ["leet","code"]
Output
true

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. Recursive brute force

Try every prefix; if it's a word, recurse on the suffix.

Time
O(2^n)
Space
O(n)
// outline — exponential without memoization.

Tradeoff: Exponential. Mention to reject.

2. 1D DP (optimal)

dp[i] = true if s[0..i-1] is segmentable. dp[i] = any j < i with dp[j] && s[j..i-1] in dict.

Time
O(n^2)
Space
O(n)
function wordBreak(s, wordDict) {
  const dict = 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] && dict.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

Tradeoff: n^2 time, n space. Could be sped up to n*maxWordLen by iterating over dict words instead of substrings.

Snowflake-specific tips

Snowflake interviewers want the DP and a discussion of why a Trie would help if the dictionary is huge (avoid re-scanning substrings for length match). Bonus signal: connect to identifier-rewrite — when Snowflake's planner rewrites WHERE clauses, it must match identifiers against catalog tables; Trie + DP is exactly the right scheme.

Common mistakes

  • Off-by-one — dp[i] represents s[:i] (the first i chars).
  • Using s.slice in a tight loop — O(n) per slice; total O(n^3) worst case.
  • Forgetting dp[0] = true (the empty prefix is segmentable).

Follow-up questions

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

  • Word Break II (LC 140) — return all segmentations.
  • How does Snowflake match identifiers in WHERE clauses?
  • Trie-based optimization.

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[0] = true?

It represents the empty prefix — segmentable into zero words. Without it, no transition can start.

Trie vs hash set?

Hash set: O(1) lookup per substring, but we still do n^2 substring extractions. Trie: walk the input once and check valid word endings at each position — overall closer to O(n * maxWordLen).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →