Marauder Bot

Problem

You are given a string and a dictionary of words, and you may reuse dictionary words as many times as needed. Determine whether the string can be split into a sequence of one or more pieces placed end to end, where every piece is exactly one of the dictionary words.

Example. For "leetcode" with dictionary ["leet", "code"], the answer is true, since the string splits as "leet" + "code".

Key idea

Trying every way to cut the string recursively re-explores the same remaining suffix many times, since different early cuts can lead to the same leftover string, so a naive search is exponential. The improvement is to track, for each position, whether the prefix ending there is reachable by some valid sequence of dictionary words.

The empty prefix, at position zero, is reachable by definition, since it needs no words. A later position is reachable if some earlier reachable position exists such that the substring between the two is itself a dictionary word. Scanning left to right, once the reachable positions to the left are known, checking the current position just means testing each earlier reachable position against the dictionary. The string as a whole is decomposable exactly when its final position turns out reachable.

Solution

function wordBreak(s: string, wordDict: string[]): boolean {
  const dictionary = new Set(wordDict);
  const reachable = new Array<boolean>(s.length + 1).fill(false);
  reachable[0] = true; // empty prefix needs no words

  for (let end = 1; end <= s.length; end++) {
    for (let start = 0; start < end; start++) {
      if (reachable[start] && dictionary.has(s.slice(start, end))) {
        reachable[end] = true; // reached via an earlier reachable position plus one dictionary word
        break; // one valid path is enough, no need to keep searching
      }
    }
  }

  return reachable[s.length];
}

Complexity

Time: O(n²). For each position, scanning back over earlier reachable positions, with a hash set giving fast average lookups for each candidate substring.
Space: O(n). One flag per position, plus the dictionary's own storage.

Watch out for

Dictionary words can be reused freely, unlike a partitioning problem where each piece is consumed; never remove a word after matching it.
The empty prefix must start out marked reachable, or nothing downstream can ever become reachable.
A hash set for the dictionary avoids a linear scan through every word for each candidate substring.

Pattern

This is a reachability DP over prefixes: the boolean cousin of Coin Change, which asks the same "can I build up to this point" question but tracks a minimum count instead of a yes-or-no answer.

Word Break