· By John Kavanagh

Word Break in TypeScript: Deciding Where Words End

Rows of carved wooden printing blocks in a traditional type tray.
Image by Declan Sun, licensed from Unsplash.

Recognising a word at the start of a string feels like progress. In LeetCode's Word Break problem, it can also be the decision that sends you down a dead end. The task is to decide whether the entire string can be divided into dictionary words, with each word available for reuse.

I find this easier to reason about when I track positions between characters. A position records how much of the string we've successfully covered. Once we know that a prefix can be split, we don't need to remember which words got us there. We just need to see whether another word can extend it.


A Plausible First Choice That Fails

Take cars and the dictionary ['car', 'ca', 'rs']. Choosing the longest matching word gives us car, followed by s, which isn't in the dictionary. Yet ca followed by rs covers the whole string. The longest match has confidently driven us into a wall.

Trying all matching words would recover the answer, but a naive recursive search repeats work. Different sequences of earlier words can leave exactly the same suffix to solve. With repeated letters and several overlapping dictionary words, that branching grows quickly, particularly when a final character makes every route fail.

This resembles the greedy trap in my Coin Change walkthrough: a locally attractive choice needs a justification before we discard its alternatives. Word Break gives us no such justification. We have to preserve enough information to revisit the other possible cuts.


Give Each Table Entry One Precise Meaning

For the bottom‑up solution, dp[i] means that the prefix s.slice(0, i) can be segmented into dictionary words. The index is a prefix length, so the table needs s.length + 1 entries. dp[0] is true: covering an empty prefix requires no words, and gives the first real word somewhere to start.

To establish dp[end], look for an earlier position start where two things hold: dp[start] is already true, and s.slice(start, end) is a dictionary word. Together they cover the entire prefix ending at end. A matching word on its own isn't enough if the text before it remains unexplained.

This also tells us why the method is complete. Any valid segmentation has a final word. Remove that word and the remaining prefix is an earlier true state, so one of our candidate cuts will find it. Conversely, every state we mark true extends a valid earlier segmentation by a real dictionary word. Processing prefix lengths in increasing order makes those earlier answers available when we need them.


The Bottom‑up Implementation

I use a Set for dictionary membership and limit candidate words to the longest dictionary entry. There is no point slicing a 30‑character candidate when the longest permitted word has 20 characters.

export const wordBreak = (s: string, wordDict: readonly string[]): boolean => {
  const words = new Set(wordDict);
  const maxLength = wordDict.reduce((longest, word) => Math.max(longest, word.length), 0);
  const dp = new Array<boolean>(s.length + 1).fill(false);
  dp[0] = true;

  for (let end = 1; end <= s.length; end += 1) {
    const firstStart = Math.max(0, end - maxLength);
    for (let start = firstStart; start < end; start += 1) {
      if (dp[start] && words.has(s.slice(start, end))) {
        dp[end] = true;
        break;
      }
    }
  }

  return dp[s.length] ?? false;
};

The break only stops the search for this particular prefix. We need one successful segmentation, so finding another cut for the same end wouldn't change its boolean answer. Later prefixes still consider every relevant earlier position.

Nothing is removed from words, and nothing changes in wordDict. This matters for applepenapple with ['apple', 'pen']: using apple once doesn't exhaust it. A dictionary is a vocabulary here, not a bag of tiles.


Following the Positions in Cars

The four‑character input gives us five states, initially [true, false, false, false, false]. The longest dictionary word has length three.

  • At end = 1, c isn't a word, so dp[1] stays false.
  • At end = 2, the cut at zero finds ca. The empty prefix is valid, so dp[2] becomes true.
  • At end = 3, car makes dp[3] true as well. Keeping both positions is useful; we haven't committed to either route.
  • At end = 4, the cut at two finds rs. Because dp[2] is true, dp[4] becomes true, and that's our answer.

Notice what we didn't do: reject the whole string after discovering that the valid prefix car leaves an invalid suffix. Another true position survived. In catsandog, using the dictionary ['cats', 'dog', 'sand', 'and', 'cat'], several prefixes are also valid, but no dictionary word connects a reachable position to the final position. Its answer stays false.


The Same Search, Discovered on Demand

A memoised recursive version starts at a position and asks whether the remaining suffix can be completed. Its state points in the opposite direction: memo[start] describes s.slice(start), not the prefix. The dictionary and candidate word lengths stay the same.

export const wordBreakMemo = (s: string, wordDict: readonly string[]): boolean => {
  const words = new Set(wordDict);
  const maxLength = wordDict.reduce((longest, word) => Math.max(longest, word.length), 0);
  const memo = new Array<boolean | undefined>(s.length);

  const canFinish = (start: number): boolean => {
    if (start === s.length) return true;
    const cached = memo[start];
    if (cached !== undefined) return cached;

    const lastEnd = Math.min(s.length, start + maxLength);
    for (let end = start + 1; end <= lastEnd; end += 1) {
      if (words.has(s.slice(start, end)) && canFinish(end)) {
        memo[start] = true;
        return true;
      }
    }

    memo[start] = false;
    return false;
  };

  return canFinish(0);
};

Check the cache with cached !== undefined, rather than if (cached). A stored false is a finished answer too. Forgetting that distinction throws away the failed branches that memoisation is meant to save us from repeating.

Both versions reuse solved positions. Memoisation may avoid positions that the successful search never needs, whilst the bottom‑up version visits each prefix length in order. I prefer the table for this explanation because its invariant is visible throughout the loop, and it avoids recursive call depth. Including the base case, the recursive version can nest up to s.length + 1 calls; passing a small interview input isn't a general guarantee about JavaScript stack limits.


Count the String Work as Well

Let n be the string length, L the longest dictionary word, m = min(n, L), and D the total number of characters in the dictionary. There are at most n * m candidate cuts in either implementation. Treating substring creation and membership as constant‑cost operations gives an abstract O(nm) search bound, or the familiar looser O(n²) description.

For JavaScript, I also budget for the characters in each candidate. Creating or hashing a previously unseen substring may require work proportional to its length. Under the usual average hash‑table model, allowing O(m) character work per candidate gives O(D + nm²) time including dictionary preparation. O(D + n²L) is a valid, looser bound; it shouldn't be confused with a claim that string operations are free. Removing the word‑length limit from the search can take the usual character‑cost estimate to O(n³).

These are cost models, not promises from a particular engine. The ECMAScript requirements for Set require average access faster than a linear scan of the collection, rather than guaranteeing constant‑time lookup. The definition of string slicing specifies the returned substring, without promising a particular storage representation or running time.

Both solutions keep O(n) boolean states and a dictionary set. A conservative allowance including dictionary characters is O(n + D) additional storage; the memoised version also has an O(n) call stack. Temporary candidate strings add at most O(m) live character storage in the table version, within that bound. Neither implementation stores every possible segmentation.


Cases I Used to Check the Reasoning

The current challenge uses lowercase English letters, a nonempty string of at most 300 characters, and between one and 1,000 distinct dictionary words, each at most 20 characters long. Empty inputs aren't official cases. My functions nevertheless return false for a nonempty string with an empty dictionary, and true for an empty string, using the zero‑word interpretation behind the base case.

I checked both implementations against every partition of short binary strings, across every nonempty subset of a six‑word dictionary. That oracle places cuts between characters and checks each resulting piece directly; it doesn't reuse the dynamic programming recurrence. For larger seeded cases, I used a separate queue‑based traversal with direct character comparisons. The maximum‑length checks include 300 repeated letters, a failing final character, and a dictionary containing 1,000 distinct words.

The shared comparison lab I've put together includes these solutions and the tests. Use the cars case to compare the greedy choice with the successful partition, then change the dictionary and run the exhaustive checks. The useful part is seeing which assumption a counterexample breaks, rather than collecting a large passing total.


Keep the Reachable Positions

In my Jump Game article, reachable positions can be summarised by a farthest frontier. Word Break doesn't have that same shape: valid cuts can have gaps, and the furthest valid prefix may lead nowhere. Keeping one boolean per position preserves the alternatives we still need.

That's the habit I'd take from this problem. Define exactly what one state says, prove how a dictionary word extends it, and only then write the loops. The table is small. The sentence explaining it does most of the work.

Downloadable Resource

  • Dynamic Programming Comparison Lab

    Run my fourteen TypeScript solutions across seven problems, with independent checks for string edits, decoding counts, staircase routes, prefixes, and subsequences.

    Download ZIP

Untangling a delivery problem?

Send the symptoms, constraints, and affected routes. I'll help identify whether the issue sits in the application, platform, content model, deployment path, or search surface.