139. Word Break
mediumAsked at ShopifyShopify 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 Sam K., 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 <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s and wordDict[i] consist of only lowercase English letters.All the strings of wordDict are unique.
Examples
Example 1
s = "leetcode", wordDict = ["leet","code"]trueExample 2
s = "applepenapple", wordDict = ["apple","pen"]trueExample 3
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]falseApproaches
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.
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.