Solving Word Break Problem in JavaScript: Step-by-Step Guide

Solving the Word Break Problem in JavaScript: A Step-by-Step Guide

The Word Break problem is one of those classic algorithmic challenges that shows up frequently in coding interviews and real-world text processing applications. At its core, it asks a deceptively simple question: given a string and a dictionary of valid words, can the string be segmented into a sequence of one or more dictionary words? In this tutorial, we'll walk through the problem from brute force to optimized dynamic programming solutions, complete with working JavaScript code.

What Is the Word Break Problem?

Formally, the Word Break problem is defined as follows: given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine whether s can be segmented into a space-separated sequence of one or more dictionary words. You may reuse the same dictionary word multiple times.

For example, given the string "leetcode" and the dictionary ["leet", "code"], the answer is true because "leetcode" can be split into "leet" + "code". However, given "catsandog" and ["cats", "dog", "sand", "and", "cat"], the answer is false because no valid segmentation exists that uses up the entire string.

Why the Problem Matters

Beyond being a popular interview question at companies like Google, Amazon, and Facebook, the Word Break problem has genuine practical applications. It is the foundation of:

• Tokenization in NLP: Splitting raw text into meaningful tokens when whitespace is missing or unreliable, such as in Chinese text processing or hashtag segmentation.
• Spell checkers and autocomplete: Determining whether a concatenated input can be decomposed into known words.
• URL slug parsing: Breaking apart concatenated slugs like "bestjavascriptframeworks" into readable words.
• OCR post-processing: Reconstructing word boundaries from text extracted by optical character recognition systems that may have lost spacing.

Understanding how to solve this problem efficiently teaches you the broader skill of recognizing when dynamic programming can replace exponential brute-force approaches — a transferable skill that applies to countless other problems.

The Naive Recursive Approach

The most intuitive first attempt is recursion. We try to match a prefix of the string against every word in the dictionary. If a prefix matches, we recursively check whether the remaining suffix can also be segmented. If at any point the entire string is consumed, we return true.

function wordBreakNaive(s, wordDict) {
  function helper(remaining) {
    if (remaining === "") return true;
    for (const word of wordDict) {
      if (remaining.startsWith(word)) {
        const suffix = remaining.slice(word.length);
        if (helper(suffix)) return true;
      }
    }
    return false;
  }
  return helper(s);
}

console.log(wordBreakNaive("leetcode", ["leet", "code"])); // true
console.log(wordBreakNaive("catsandog", ["cats", "dog", "sand", "and", "cat"])); // false

This works for short inputs, but it has a fatal flaw: exponential time complexity. In the worst case, the same substring is recomputed many times across different branches of the recursion tree. For a string of length n, the worst-case time complexity is O(2^n), which becomes unusable for strings longer than about 25 characters.

Adding Memoization

The first optimization is to cache the results of subproblems. Since the recursive function only depends on the remaining substring, we can store whether each suffix is breakable. This technique, called memoization, reduces the time complexity to O(n^2 * m) where n is the string length and m is the average word length.

function wordBreakMemo(s, wordDict) {
  const memo = new Map();

  function helper(start) {
    if (start === s.length) return true;
    if (memo.has(start)) return memo.get(start);

    for (const word of wordDict) {
      const end = start + word.length;
      if (end <= s.length && s.slice(start, end) === word) {
        if (helper(end)) {
          memo.set(start, true);
          return true;
        }
      }
    }
    memo.set(start, false);
    return false;
  }

  return helper(0);
}

console.log(wordBreakMemo("leetcode", ["leet", "code"])); // true
console.log(wordBreakMemo("applepenapple", ["apple", "pen"])); // true

Notice we now track positions using an index start rather than slicing the string repeatedly. This is both cleaner and more efficient, since slicing creates new strings each time.

The Bottom-Up Dynamic Programming Solution

The canonical solution to Word Break uses bottom-up dynamic programming. We define a boolean array dp where dp[i] represents whether the substring s[0..i-1] (the first i characters) can be segmented. The base case is dp[0] = true, meaning the empty string is always segmentable.

For each position i from 1 to n, we check every position j from 0 to i - 1. If dp[j] is true (meaning the prefix up to j is breakable) and the substring s[j..i-1] is in the dictionary, then dp[i] is true.

function wordBreakDP(s, wordDict) {
  const wordSet = new Set(wordDict);
  const n = s.length;
  const dp = new 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] && wordSet.has(s.slice(j, i))) {
        dp[i] = true;
        break; // No need to check further, dp[i] is already true
      }
    }
  }

  return dp[n];
}

console.log(wordBreakDP("leetcode", ["leet", "code"])); // true
console.log(wordBreakDP("catsandog", ["cats", "dog", "sand", "and", "cat"])); // false
console.log(wordBreakDP("cars", ["car", "ca", "rs"])); // true

This solution runs in O(n^2) time and uses O(n) space. Converting the dictionary into a Set gives us O(1) average-time lookups, which is critical for performance. The inner break statement is a small but meaningful optimization: once we know dp[i] is true, there is no reason to keep checking other split points.

Tracing Through an Example

To solidify your understanding, let's trace through wordBreakDP("leetcode", ["leet", "code"]) step by step:

• Initialize dp = [true, false, false, false, false, false, false, false, false] (length 9 for an 8-character string).
• i = 1 to i = 3: No substring s[0..i-1] is in the dictionary, so dp[1..3] remain false.
• i = 4: Check j = 0. dp[0] is true and s.slice(0, 4) = "leet" is in the set. Set dp[4] = true.
• i = 5 to i = 7: No valid split found, dp[5..7] remain false.
• i = 8: Check j = 4. dp[4] is true and s.slice(4, 8) = "code" is in the set. Set dp[8] = true.
• Return dp[8] = true.

Optimizing with Word Length Bounds

The inner loop checks every j from 0 to i - 1, but many of those checks are wasteful if no dictionary word has that length. We can precompute the minimum and maximum word lengths and only consider split points where the substring length falls within that range.

function wordBreakOptimized(s, wordDict) {
  const wordSet = new Set(wordDict);
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;

  let minLen = Infinity;
  let maxLen = 0;
  for (const word of wordDict) {
    minLen = Math.min(minLen, word.length);
    maxLen = Math.max(maxLen, word.length);
  }

  for (let i = 1; i <= n; i++) {
    for (let j = Math.max(0, i - maxLen); j <= i - minLen; j++) {
      if (dp[j] && wordSet.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }

  return dp[n];
}

console.log(wordBreakOptimized("leetcode", ["leet", "code"])); // true

This optimization is especially valuable when the dictionary contains words of similar lengths, because it dramatically reduces the number of substring comparisons in the inner loop.

Reconstructing the Actual Segmentation

Sometimes knowing that a segmentation exists is not enough — you want to return the actual words. We can extend the DP solution to track which split point was used at each position, then backtrack to reconstruct the word list.

function wordBreakSegment(s, wordDict) {
  const wordSet = new Set(wordDict);
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  const parent = new Array(n + 1).fill(-1);
  dp[0] = true;

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

  if (!dp[n]) return null;

  const segments = [];
  let end = n;
  while (end > 0) {
    const start = parent[end];
    segments.unshift(s.slice(start, end));
    end = start;
  }
  return segments;
}

console.log(wordBreakSegment("leetcode", ["leet", "code"]));
// ["leet", "code"]

console.log(wordBreakSegment("applepenapple", ["apple", "pen"]));
// ["apple", "pen", "apple"]

The parent array stores, for each breakable position, the index where the last word began. By walking backward from n to 0, we collect the words in reverse order and use unshift to place them correctly. If you need all possible segmentations rather than just one, you would replace the break with a recursive enumeration — but be warned, the number of valid segmentations can grow exponentially.

Handling Edge Cases

Robust production code needs to handle edge cases gracefully. Consider the following scenarios:

• Empty string: By convention, an empty string is considered breakable, so return true.
• Empty dictionary: No words means no segmentation is possible (except for the empty string), so return false.
• Single-character strings: Make sure your loops handle n = 1 correctly without off-by-one errors.
• Words longer than the string: The end <= s.length check prevents out-of-bounds slicing.
• Repeated characters: Strings like "aaaaaaa" with dictionary ["aaaa", "aaa"] can produce many valid segmentations and stress-test your performance.

function wordBreakRobust(s, wordDict) {
  if (s.length === 0) return true;
  if (wordDict.length === 0) return false;

  const wordSet = new Set(wordDict);
  const n = s.length;
  const dp = new 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] && wordSet.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }

  return dp[n];
}

console.log(wordBreakRobust("", ["a"])); // true
console.log(wordBreakRobust("a", [])); // false
console.log(wordBreakRobust("a", ["a"])); // true

Best Practices

When implementing Word Break in real projects or interviews, keep these best practices in mind:

• Always convert the dictionary to a Set: Array lookups are O(m), while Set lookups are O(1) on average. This single change can make orders-of-magnitude differences on large inputs.
• Prefer index-based recursion over string slicing: Slicing creates new strings and adds overhead. Passing indices into the original string is faster and uses less memory.
• Use the bottom-up DP for interviews: It is the most idiomatic solution, easy to explain, and avoids recursion stack limits on long strings.
• Add early termination: If the string contains characters not present in any dictionary word, you can return false immediately. Compute the set of all characters in the dictionary once and compare.
• Consider Trie structures for huge dictionaries: If your dictionary has tens of thousands of words, a Trie lets you check all matching prefixes in a single pass over the string, often outperforming the Set-based approach.
• Test with pathological inputs: Strings like "aaaaaaaaaaaaaaaaaaaaaaaaaaaaab" with a dictionary like ["a", "aa", "aaa", "aaaa"] are designed to expose performance weaknesses. Make sure your solution handles them in reasonable time.

A Trie-Based Variation

For completeness, here is a sketch of how a Trie can be used to solve Word Break. Instead of checking every split point against the dictionary, we walk forward from each breakable position through the Trie, marking new positions as breakable whenever we hit a word-ending node.

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isWord = false;
  }
}

function buildTrie(wordDict) {
  const root = new TrieNode();
  for (const word of wordDict) {
    let node = root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
    }
    node.isWord = true;
  }
  return root;
}

function wordBreakTrie(s, wordDict) {
  const root = buildTrie(wordDict);
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;

  for (let i = 0; i < n; i++) {
    if (!dp[i]) continue;
    let node = root;
    for (let j = i; j < n; j++) {
      const ch = s[j];
      if (!node.children.has(ch)) break;
      node = node.children.get(ch);
      if (node.isWord) dp[j + 1] = true;
    }
  }

  return dp[n];
}

console.log(wordBreakTrie("leetcode", ["leet", "code"])); // true
console.log(wordBreakTrie("catsandog", ["cats", "dog", "sand", "and", "cat"])); // false

This approach shines when the dictionary is large and contains many words with shared prefixes, because it avoids redundant substring comparisons. The time complexity becomes O(n * L) where L is the maximum word length, which is often much smaller than n.

Conclusion

The Word Break problem is a perfect showcase for the power of dynamic programming. What starts as an intimidating exponential recursion collapses into an elegant O(n^2) solution once you recognize the overlapping subproblems and optimal substructure. By mastering the bottom-up DP approach, adding practical optimizations like word-length bounds and Set-based lookups, and knowing when to reach for a Trie, you'll be equipped to handle this problem confidently in both interviews and production systems. More importantly, the pattern of identifying repeated work and caching results transfers directly to a wide range of algorithmic challenges, making Word Break a worthwhile investment of your study time.