Skip to main content

139. Word Break

mediumAsked at Shopify

Shopify uses Word Break to test DP intuition. Real motivation: 'is this discount-code string composed entirely of valid SKU tokens?' or 'can we segment this search query into known product names?'.

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

Source citations

Public interview reports confirming this problem appears in Shopify loops.

  • Glassdoor (2026-Q1)— Shopify Senior Backend onsites cite Word Break as a recurring DP round.
  • Reddit r/cscareerquestions (2025-11)— Shopify new-grad reports include this with a string-segmentation follow-up.

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 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

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. Naive recursion (exponential)

Try every prefix that matches a dictionary word; recurse on the suffix.

Time
O(2^n)
Space
O(n) recursion depth
function wordBreakNaive(s, wordDict) {
  const set = new Set(wordDict);
  function rec(i) {
    if (i === s.length) return true;
    for (let j = i + 1; j <= s.length; j++) {
      if (set.has(s.slice(i, j)) && rec(j)) return true;
    }
    return false;
  }
  return rec(0);
}

Tradeoff: Exponential because the same suffix can be re-explored many times. Don't ship; use to motivate memoization.

2. Top-down memoization

Cache rec(i) so each suffix is computed once.

Time
O(n^2 * L)
Space
O(n)
function wordBreakMemo(s, wordDict) {
  const set = new Set(wordDict);
  const memo = new Map();
  function rec(i) {
    if (i === s.length) return true;
    if (memo.has(i)) return memo.get(i);
    for (let j = i + 1; j <= s.length; j++) {
      if (set.has(s.slice(i, j)) && rec(j)) {
        memo.set(i, true);
        return true;
      }
    }
    memo.set(i, false);
    return false;
  }
  return rec(0);
}

Tradeoff: Same complexity as the iterative DP but with the cost of the function-call overhead. Easier to reason about than tabulation. Acceptable as the optimal.

3. Bottom-up DP (canonical optimal)

dp[i] = true if s[0..i-1] is breakable. dp[i] = true iff there's some j < i where dp[j] is true and s[j..i-1] is in the dictionary.

Time
O(n^2 * L)
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: Iterative, no recursion stack. Same O(n^2 * L) where L is the substring extraction cost. Shopify expects this. The dp[0] = true base case represents the empty prefix being trivially breakable.

4. Trie-accelerated DP

Build a trie from wordDict; at each i, walk the trie character by character and union all (i, end-of-word) transitions into dp[end + 1].

Time
O(n^2)
Space
O(sum of word lengths)
// Use the Trie class from the Trie problem.
function wordBreakTrie(s, wordDict) {
  const root = {};
  for (const w of wordDict) {
    let node = root;
    for (const ch of w) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node.end = true;
  }
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 0; i < s.length; i++) {
    if (!dp[i]) continue;
    let node = root;
    for (let j = i; j < s.length; j++) {
      const ch = s[j];
      if (!node[ch]) break;
      node = node[ch];
      if (node.end) dp[j + 1] = true;
    }
  }
  return dp[s.length];
}

Tradeoff: Drops the substring extraction and the Set lookup. Faster in practice when wordDict has many words with shared prefixes. Mention it as the senior-level optimization.

Shopify-specific tips

Shopify's expected follow-up: 'now return ALL valid segmentations' (LeetCode 140) — that's where the trie + memoized recursion pays off. They also probe 'what if the dictionary is huge but s is short' — the trie traversal becomes O(s.length * avg word length) and dominates the naive Set version. Volunteer that case unprompted.

Common mistakes

  • Initializing dp[0] = false — every solution requires the empty-prefix base case.
  • Breaking out of the j-loop early on dp[i] = true without recording it.
  • Slicing the string on every check — for very large s, profile-allocating substrings hurts. Trie walks dodge this.
  • Using a list of words instead of a Set for the dictionary — O(D) lookup per substring becomes the bottleneck.

Follow-up questions

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

  • Word Break II (LeetCode 140) — return all segmentations.
  • Concatenated Words (LeetCode 472) — find all words in a list that are concatenations of other words in the list.
  • What if words can overlap in some defined way?
  • Streaming version — s arrives a character at a time; report breakability incrementally.

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 the time complexity O(n^2 * L)?

n^2 from the double loop over i and j. L from s.slice(j, i) which is O(L) where L is the substring length. Replacing slice with trie traversal drops the L factor.

Word Break vs Word Break II — different algorithms?

Same DP structure, but II must reconstruct all paths, so you need a back-pointer per dp[i] storing every (j, word) that led there. The exponential blowup happens because there can be exponentially many segmentations.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →