Skip to main content

75. Word Break

mediumAsked at Plaid

Determine if a string can be segmented into a sequence of dictionary words. Plaid asks this because tokenizing a merchant string into known sub-tokens (e.g., 'AMZNMKTPLACE' -> 'AMZN' + 'MKT' + 'PLACE') is the same primitive.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE II onsite — framed as merchant tokenization.
  • Blind (2026)— Plaid data-engineering OA.

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. Recursive without memo

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

Time
O(2^n)
Space
O(n)
// Exponential. Mention as warm-up.

Tradeoff: TLE.

2. 1D DP with set lookup

dp[i] = can s[0..i] be segmented? dp[i] = true if dp[j] and s[j..i] in dict for some j.

Time
O(n^2 * k) where k is max word len
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: O(n^2) substring iterations, each a hash lookup. Acceptable for n <= 300.

Plaid-specific tips

Plaid grades this on the DP formulation. Bonus signal: discuss the optimization of limiting j to the range [i - maxWordLen, i] to skip impossible substrings. Connect to merchant tokenization where you need to split 'STARBUCKSCAFE' into 'STARBUCKS' + 'CAFE' using a dictionary of known tokens.

Common mistakes

  • Using indexOf or includes on the array — O(k) per call. Use a Set.
  • Forgetting dp[0] = true — the empty prefix is trivially segmentable.
  • Not breaking on dp[i] = true — wasted iterations.

Follow-up questions

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

  • Word Break II (LC 140) — return all possible segmentations.
  • Min number of words to segment.
  • 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 and not greedy?

Greedy fails on cases like 'applepenapple' with dict ['apple', 'app', 'penapple'] — picking the longest match first can miss valid segmentations.

Can a Trie speed this up?

Yes — instead of testing every suffix, walk the Trie from each position. Skips impossible prefixes early.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →