Skip to main content

66. Word Break

mediumAsked at Workday

Determine if a string can be segmented into a sequence of dictionary words. Workday uses this for DP-on-strings — same shape as validating that a free-form job-title string can be decomposed into known role tokens.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025-Q4)— Workday SDE2 onsite — DP staple.

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; if it's in dict, recurse on suffix.

Time
O(2^n)
Space
O(n)
function f(s){ if (s==='') return true; for (const w of dict) if (s.startsWith(w) && f(s.slice(w.length))) return true; return false; }

Tradeoff: Exponential. Don't ship.

2. Bottom-up DP

dp[i] = true if s[..i] is segmentable. dp[i] = any j < i where dp[j] && s[j..i] in dict.

Time
O(n^2)
Space
O(n + dict)
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). Each i scans backward to find a split point. The set converts dict to O(1) lookup.

Workday-specific tips

Workday wants the DP version. Convert the dict to a Set upfront — using includes() on the array is O(dict). The break inside the inner loop is the optimization that saves redundant work.

Common mistakes

  • Using wordDict.includes() — O(dict) per check, makes the inner loop expensive.
  • Forgetting dp[0] = true.
  • Off-by-one in the substring slice.

Follow-up questions

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

  • Word Break II (LC 140) — return all sentences.
  • Concatenated Words (LC 472).
  • 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[0] = true?

The empty prefix is trivially segmentable (no words needed). All segmentations of s[..i] start from some valid prefix; dp[0]=true is the base case.

Trie for big dictionaries?

Yes — trie reduces the inner-loop substring check to O(matched chars). Useful when dict is huge.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →