Word Break II

You're given a string s and a list of dictionary words wordDict. Insert spaces into s so that every piece is a word from the dictionary, and return every sentence you can make this way.

A dictionary word may be used any number of times. Each sentence is the pieces joined by single spaces, with no leading or trailing space. If s cannot be split at all, return an empty list.

Return the sentences in any order.

Every sentence starts with some dictionary word that is a prefix of s. Once you pick that first word, what remains is the same problem on a shorter suffix. So the natural shape is recursive: "all sentences for s[i:]" = for each word that starts at i, that word followed by each sentence for the rest.

The catch is repeated work. Different first choices often land on the same suffix ("a" + "a" and "aa" both reach index 2), and plain backtracking re-solves that suffix every time. Worse, a string like "aaaa...ab" has millions of partial splits that all die at the final b.

Caching the list of sentences for each start index fixes both: each suffix is solved once, and a suffix with no solutions is remembered as empty, so dead ends are pruned immediately.

def word_break(s: str, word_dict: list[str]) -> list[str]:
    words = set(word_dict)
    longest = max(map(len, words))
    memo: dict[int, list[str]] = {len(s): [""]}

    def solve(i: int) -> list[str]:
        if i in memo:
            return memo[i]
        sentences = []
        for j in range(i + 1, min(len(s), i + longest) + 1):
            word = s[i:j]
            if word in words:
                for rest in solve(j):
                    sentences.append(word + " " + rest if rest else word)
        memo[i] = sentences
        return sentences

    return solve(0)

function wordBreak(s, wordDict) {
  const words = new Set(wordDict);
  const longest = Math.max(...wordDict.map((w) => w.length));
  const memo = new Map([[s.length, ['']]]);

  function solve(i) {
    if (memo.has(i)) return memo.get(i);
    const sentences = [];
    for (let j = i + 1; j <= Math.min(s.length, i + longest); j++) {
      const word = s.slice(i, j);
      if (!words.has(word)) continue;
      for (const rest of solve(j)) {
        sentences.push(rest ? word + ' ' + rest : word);
      }
    }
    memo.set(i, sentences);
    return sentences;
  }

  return solve(0);
}

Start from Word Break I if you know it: "the boolean version is a DP over suffixes; this version keeps the actual sentences instead of true/false." That framing shows you see the connection.

Be honest about complexity. Interviewers listen for you saying that the number of sentences can be exponential, so the goal is to avoid wasted work, not to make the output smaller. Then call out the input that breaks plain backtracking, a long run of as ending in a letter that is not in the dictionary, and explain how memoizing empty results handles it.