Word Break

The problem

Given string s and word dictionary wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Words may be reused.

Input:  s = "leetcode", wordDict = ["leet","code"]
Output: true

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

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

Brute force: recursion

From index i, try every word that matches s starting at i; recurse. Memoize on i.

function wordBreakMemo(s: string, wordDict: string[]): boolean {
  const words = new Set(wordDict);
  const memo = new Map<number, boolean>();

  function dfs(i: number): boolean {
    if (i === s.length) return true;
    if (memo.has(i)) return memo.get(i)!;
    for (let j = i + 1; j <= s.length; j++) {
      if (words.has(s.slice(i, j)) && dfs(j)) {
        memo.set(i, true);
        return true;
      }
    }
    memo.set(i, false);
    return false;
  }
  return dfs(0);
}

Optimal bottom-up DP

dp[i] = true if s[0..i) can be segmented.

function wordBreak(s: string, wordDict: string[]): boolean {
  const words = new Set(wordDict);
  const n = s.length;
  const dp = Array(n + 1).fill(false);
  dp[0] = true;

  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && words.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[n];
}

Optimize inner loop with max word length:

function wordBreakOpt(s: string, wordDict: string[]): boolean {
  const words = new Set(wordDict);
  let maxLen = 0;
  for (const w of wordDict) maxLen = Math.max(maxLen, w.length);
  const n = s.length;
  const dp = Array(n + 1).fill(false);
  dp[0] = true;

  for (let i = 1; i <= n; i++) {
    for (let len = 1; len <= maxLen && len <= i; len++) {
      if (dp[i - len] && words.has(s.slice(i - len, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[n];
}

Time	O(n² · L) slice costs; better with trie / maxLen
Space	O(n + dictionary)

Edge cases

• Empty s → true
• Word longer than s
• Overlapping candidates (cat / cats)
• Reuse of same word

Common bugs

• Forgetting word reuse is allowed
• Only greedy left-to-right (fails on some dicts)
• Not using a set → slow includes

Interview delivery

1. DP boolean prefix.
2. Or memo DFS.
3. Set for O(1) lookups.
4. Complexity.
5. Follow-up: Word Break II (list all segmentations).

Related

• Word Ladder
• Palindrome Partitioning
• Coin Change
• Unique Paths

Greedy fails

s = "aaaaaaa", dict ["aaaa","aaa"] can be segmented; naive always taking longest may or may not depending on implementation. DP explores all split points — safe.

Graph view

Indices 0..n are nodes; edge j→i if s[j..i) in dict. dp[i] = reachable from 0. Word Break is path existence in that DAG.

Word Break II

Same DP reachability, then DFS to reconstruct all sentences. Only recurse indices where dp[i] is true to prune.

Further reading

• LeetCode 139 — Word Break
• MDN: Set