Skip to main content

139. Word Break

mediumAsked at Linear

Determine if a string can be segmented into words from a dictionary. Linear uses this DP problem to see if you can formulate dp[i] = 'can I form s[0..i-1] from the wordDict?' and handle the substring check efficiently.

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

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2025-12)— Cited in Linear SWE onsite reports as a DP string problem.
  • Blind (2025-10)— Mentioned in Linear interview preparation threads as a mid-difficulty DP question.

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

Example 2

Input
s = "applepenapple", wordDict = ["apple","pen"]
Output
true

Explanation: 'apple pen apple' — the word 'apple' is reused.

Example 3

Input
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output
false

Approaches

1. Naive recursion with memoization

Try every possible split point. Recurse on the suffix if the prefix is in wordDict. Memoize on the current index.

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

Tradeoff: Top-down DP. Memoization prevents redundant recomputation. O(n^2) substrings * O(m) set lookup per substring worst case.

2. Bottom-up DP (canonical)

dp[i] = true if s[0..i-1] can be segmented. For each i, check all j < i where dp[j] is true and s[j..i-1] is in the word set.

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

Tradeoff: O(n^2) time (n^2 substring checks), O(n) space. Iterative, no recursion overhead. dp[0] = true is the key base case — the empty prefix requires no words.

Linear-specific tips

Define the DP state before coding: 'dp[i] is true if the first i characters of s can be formed using words in the dictionary.' Then explain the transition: 'dp[i] is true if there exists some j < i where dp[j] is true and s[j..i] is in wordDict.' Linear grades this problem on DP state definition clarity, not just working code.

Common mistakes

  • Not setting dp[0] = true — the empty prefix is the base case; without it, no word can ever be matched.
  • Using indexOf instead of a Set for word lookup — O(n) per lookup makes the overall solution O(n^3).
  • Not using slice correctly — s.slice(j, i) gives characters from index j to i-1 (inclusive).

Follow-up questions

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

  • Word Break II (LC 140) — return all valid segmentations (backtracking + memoization).
  • What if the wordDict is very large but words are short? (Trie lookup instead of set.)
  • How does adding a Trie improve the solution when many words share prefixes?

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?

It represents the empty prefix, which trivially satisfies 'can be segmented.' Without it, no word starting at index 0 would ever fire the dp[j] && wordSet.has(...) condition.

Can I use a Trie instead of a Set?

Yes — a Trie gives O(L) lookup per word where L is word length, and naturally prunes branches that don't match any prefix. Worth mentioning as an optimization for very large dictionaries.

What's the difference between top-down and bottom-up here?

Both are O(n^2). Top-down memoization is often easier to reason about from the recursion. Bottom-up fills a table iteratively. Either is acceptable at Linear.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →