Solution

You'll decide whether a spaceless string can be cut into a sequence of dictionary words, by remembering — for each position in the string — whether everything before it can already be segmented.

The problem, in plain English

Someone hands you "applepenapple" and a dictionary { "apple", "pen" }. You want a yes/no answer: can you place a few cuts so that every chunk between cuts is a real word? Here the answer is yes — cut after apple, after pen, and the last chunk is apple again. The same word can be used more than once, and the cuts have to reach the very end of the string; covering just a prefix doesn't count.

The catch is the number of ways to place cuts. A string of length n has n − 1 interior gaps, and each gap is independently a cut-or-not — that's up to 2^(n−1) candidate segmentations. We can't try them all. The way out is to notice that the same sub-strings get re-examined over and over, and to compute each one only once.

The mental model

Forget the words for a second and think about positions. Number the gaps in the string 0 (before the first character) through n (after the last). For each position i, ask one question: can the part of the string before i — that is s.slice(0, i) — be fully segmented into dictionary words? Call the answer breakable[i].

Two facts make this tractable. First, breakable[0] is true by definition: the empty prefix is the empty sequence of words. Second, breakable[i] is true exactly when there's some earlier position j where breakable[j] is already true and the chunk s.slice(j, i) between them is a dictionary word. In words: "I can reach position i if I could reach some earlier j, and the word from j to i is in the dictionary." The final answer is breakable[n] — can we reach the end?

A first attempt

The obvious approach is recursion: to segment a string, try every dictionary word as the first chunk, and if a word matches the start, recurse on whatever remains.

function canSegment(s, words) {
  if (s === '') return true;            // empty string: nothing left, success
  for (const word of words) {
    if (s.startsWith(word)) {
      // peel off `word` and try to segment the rest
      if (canSegment(s.slice(word.length), words)) return true;
    }
  }
  return false;                          // no first word led to a full segmentation
}

This is correct — it really does return the right answer. The problem is speed. Consider "applepenapple": the call on the suffix "apple" (the last five characters) happens once after peeling applepen, but on longer or more ambiguous strings the same suffix gets re-solved through many different prefixes. With a dictionary like { "a", "aa" } and an input of many as, the number of recursive paths to the same suffix explodes — the work is exponential in the length of the string. We're solving the identical subproblem ("can this suffix be segmented?") again and again.

The working solution

The fix is to compute each position's answer once and store it in an array. We build breakable from left to right; by the time we ask about position i, every earlier position's answer is already known.

function stringSegmentWords(s, dict) {
  // O(1) membership: a Set, whether dict came in as an array or a Set already.
  const words = new Set(dict);
  const n = s.length;

  // breakable[i] === true  ⇔  s.slice(0, i) splits fully into dictionary words.
  const breakable = new Array(n + 1).fill(false);
  breakable[0] = true; // the empty prefix is the empty (valid) sequence of words

  for (let i = 1; i <= n; i++) {
    // Find a split point j < i: prefix up to j is breakable AND
    // the chunk s.slice(j, i) is a dictionary word.
    for (let j = 0; j < i; j++) {
      if (breakable[j] && words.has(s.slice(j, i))) {
        breakable[i] = true;
        break; // one valid split is enough; stop scanning j
      }
    }
  }

  return breakable[n]; // can we reach the very end?
}

module.exports = { stringSegmentWords };

The shift from the naive version is that the recursion's repeated subproblems become array lookups. Where the recursion asked "can this suffix be segmented?" and recomputed the answer, the DP has already stored "can the prefix up to j be segmented?" in breakable[j] — reading it is O(1). The outer loop walks each end position i; the inner loop walks each candidate start j; the words.has(s.slice(j, i)) check decides whether the chunk between them is a real word.

A few choices worth calling out:

• new Set(dict) accepts both shapes. new Set([...]) builds a set from an array, and new Set(someSet) copies an existing set — so the same line handles a dictionary passed as an array or as a Set, and either way membership tests are O(1) instead of scanning a list.
• breakable[0] = true is the seed, not a special case. Every true later in the array traces back to this one. Without it, the inner loop's breakable[j] is never true for j = 0, and nothing ever becomes reachable.
• break once a split is found. We only need whether a segmentation exists, not how many. The first j that works settles breakable[i]; scanning further j values can't change a true to anything better.
• Empty string falls out for free. If s is "", then n is 0, the loop body never runs, and we return breakable[0], which is true — exactly the documented contract.

Walking through one call

Trace stringSegmentWords("leetcode", { "leet", "code" }). The string has length 8, so breakable has 9 slots, indices 0 through 8. Start with breakable[0] = true and everything else false.

i = 1..3   prefixes "l", "le", "lee" — no j gives both
           breakable[j]=true and a dict word. All stay false.

i = 4      j = 0: breakable[0]=true AND s.slice(0,4)="leet" ∈ dict
           → breakable[4] = true, break

i = 5..7   prefixes ".....", e.g. i=5 tries j=0 ("leetc", no),
           j=4 (breakable[4]=true, s.slice(4,5)="c", not a word).
           None succeed. breakable[5..7] stay false.

i = 8      j = 0: s.slice(0,8)="leetcode" not in dict
           j = 4: breakable[4]=true AND s.slice(4,8)="code" ∈ dict
           → breakable[8] = true, break

return breakable[8] === true

The chain is breakable[0] → breakable[4] → breakable[8]: the empty prefix unlocks "leet", and reaching position 4 unlocks "code", which reaches the end.

Now contrast a string that fails: stringSegmentWords("catsandog", { "cats", "dog", "sand", "and", "cat" }). The prefixes get further than you'd expect — breakable[3] is true ("cat"), breakable[4] is true ("cats"), breakable[7] is true ("cat"+"sand" or "cats"+"and") — but the final two characters "og" are not a dictionary word, and no breakable[j] with j ≤ 7 plus a dictionary chunk can reach position 9. So breakable[9] stays false, and the answer is false.

Gotchas

• Matching a prefix is not the answer — reaching the end is. With "catsandog" you can match "cats" and "and" and feel like you're winning, but "og" is left over and breakable[9] never flips. Always return breakable[n], never "did any word match somewhere."
• Forgetting breakable[0] = true makes everything false. That seed is the base case the whole array is built on. Skip it and no position ever becomes reachable, so every input returns false — including obviously segmentable ones.
• Scanning the dictionary as an array is O(word-count) per check. If you write dict.includes(s.slice(j, i)) instead of building a Set, each membership test is linear in the dictionary size, turning the algorithm into O(n² × dictionary-length). Build a Set once and use .has.
• The inner loop must run j from 0 up to i, not from i backwards to some fixed window. Dictionary words can be any length, so the chunk s.slice(j, i) could start anywhere before i. Capping j to "the last few characters" silently misses long words. (An optional optimisation: cap the chunk length at the longest dictionary word — but get the full loop right first.)
• Reuse is automatic, not something you add. Because breakable[j] being true says nothing about which words got you there, the same word naturally appears multiple times — "applepenapple" uses "apple" twice with no special handling.
• new Set(dict) already handles the Set-or-array input. Don't branch on Array.isArray(dict); new Set(...) accepts either an array or an existing set and gives you a fresh set both ways.

Going further

• Return the actual segmentation. Keep a from array where from[i] records the j that made breakable[i] true. After the table fills, walk backwards from n following from, slicing out each word, and reverse — that reconstructs one valid sentence rather than just a yes/no. This is the standard "store the choice, not just the value" DP trick.
• Word Break II — all segmentations. Instead of a boolean, return every way to segment s (e.g. ["cats and dog", "cat sand dog"]). This is a different complexity class: the number of segmentations can itself be exponential, so it's typically solved with memoized recursion that returns lists of sentences, with the memo keyed by the suffix.
• Trie + DFS for large dictionaries. When the dictionary is huge, building a trie of the words lets you advance character-by-character from each start position and prune the moment no word can continue, instead of slicing and hashing every candidate chunk. Same DP shape, cheaper inner step.