Skip to main content

78. Word Break

mediumAsked at Vercel

Given a string and a dictionary, return whether the string can be segmented into space-separated dictionary words. Vercel asks this for the 1D DP with backward dependency — same shape as their incremental URL-path segmentation logic.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; DP expected.
  • Blind (2026-Q1)— Listed in Vercel routing engineer screen.

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

Example 3

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

Approaches

1. Recursion without memo

Try every prefix; recurse on the suffix.

Time
O(2^n)
Space
O(n)
// Exponential; memoize.

Tradeoff: Exponential blow-up; mention only to motivate DP.

2. 1D DP forward (optimal)

dp[i] = true if s[0..i) can be segmented. dp[0] = true. dp[i] = true if exists j < i with dp[j] AND s[j..i) in dict.

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.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

Tradeoff: O(n^2) splits, O(L) substring per check. Set lookup is O(L). Bound the inner loop by max word length for a real speedup.

Vercel-specific tips

Vercel grades the DP. Bonus signal: bounding the inner loop by max(wordDict.length) — saves a constant factor when the dict has short words. Also flag that Trie-based matching is the canonical optimization for very long s.

Common mistakes

  • Forgetting dp[0] = true — every segmentation fails.
  • Looping j from 1 instead of 0 — misses the case where the entire prefix [0..i) is a single word.
  • Forgetting the early break on dp[i] = true — wastes work.

Follow-up questions

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

  • Word Break II (LC 140) — return all valid segmentations.
  • Concatenated Words (LC 472) — find words formed by other dict words.
  • Trie-based version for very long strings.

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 forward DP?

dp[i] represents 'can the first i characters be segmented' — a natural left-to-right scan. Each new position checks if any earlier-segmented prefix combines with a dict word ending here.

Trie alternative?

Build a Trie of wordDict. For each i, walk the Trie down through s starting at i; whenever you hit a word-end, mark dp[i + word_length] = true. Same complexity, fewer substring allocations.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →