139. Word Break

At a Glance

Topic: Array
Pattern: Analyze Pattern
Difficulty: Medium
LeetCode: 139

Problem Statement

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.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

Example 3:

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

Constraints:

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordD...

Approach & Solution Steps

Brute force — try all splits — exponential.
Better — BFS/DFS with memo on start index — O(n^3) worst with substring checks, O(n * m) with clever hashing.
Optimal — reachable[end] boolean DP — O(n^2 * average_word_check) time; with trie can prune. <- pick this in interview.

Optimal JS Solution

function wordBreakTable(s, wordDict) {
  const length = s.length;
  const wordSet = new Set(wordDict);
  const reachable = new Array(length + 1).fill(false);
  reachable[0] = true;
  for (let end = 1; end <= length; end++) {
    for (let start = 0; start < end; start++) {
      if (!reachable[start]) continue;
      const segment = s.slice(start, end);
      if (wordSet.has(segment)) {
        reachable[end] = true;
        break;
      }
    }
  }
  return reachable[length];
}

function wordBreak(s, wordDict) {
  const length = s.length;
  const wordSet = new Set(wordDict);
  let maxWord = 0;
  for (const word of wordDict) {
    maxWord = Math.max(maxWord, word.length);
  }
  const reachable = new Array(length + 1).fill(false);
  reachable[0] = true;
  for (let start = 0; start < length; start++) {
    if (!reachable[start]) continue;
    const limit = Math.min(length, start + maxWord);
    for (let end = start + 1; end <= limit; end++) {
      const segment = s.slice(start, end);
      if (wordSet.has(segment)) {
        reachable[end] = true;
      }
    }
  }
  return reachable[length];
}

Edge Cases & Pitfalls

Always consider empty or null inputs.
Watch out for off-by-one index errors.