Skip to main content

67. Word Break

mediumAsked at Salesforce

Determine if a string can be segmented into a sequence of dictionary words. Salesforce uses this as the canonical DP-on-strings problem.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses word-segmentation patterns in their tag-parsing pipeline.
  • Blind (2025-11)— Common Salesforce L4/L5 onsite 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
  • 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

For each dictionary prefix that matches s, recurse on the rest.

Time
O(2^n)
Space
O(n)
function wordBreak(s, wordDict) {
  function dp(i) {
    if (i === s.length) return true;
    for (const w of wordDict) {
      if (s.startsWith(w, i) && dp(i + w.length)) return true;
    }
    return false;
  }
  return dp(0);
}

Tradeoff: Exponential. Memoize.

2. Bottom-up DP

dp[i] = true if s[0..i] is segmentable. dp[i] = true if for some j < i, dp[j] is true AND s[j..i] is in dict.

Time
O(n^2 * k)
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 * k) where k is the cost of slice + set lookup. Acceptable. Could be reduced to O(n * maxWordLen) by only checking j positions near i.

Salesforce-specific tips

Salesforce uses similar segmentation in their tag-parsing pipeline (splitting a hashtag string into component words). They grade on whether you can articulate the DP recurrence cleanly. Bonus signal: discuss the trie-based version which avoids the slice overhead — useful for very long strings.

Common mistakes

  • Forgetting dp[0] = true — the empty prefix is segmentable trivially.
  • Looping j from 1 instead of 0 — misses single-word segmentations.
  • Using indexOf on a list — Set is O(1), list is O(k).

Follow-up questions

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

  • Word Break II (LC 140) — return all segmentations.
  • Concatenated Words (LC 472).
  • Use a Trie to speed up matching.

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?

Convention: the empty string is trivially segmentable (zero words). This makes the recurrence start cleanly.

Can I optimize by only iterating j over starts of likely words?

Yes — for each i, j only matters if i - j == length of some word in dict. Maintain a set of word lengths to skip invalid j.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →