Word break II (all sentences)

Hard TimeO(n²·k) SpaceO(n·k)

Given a string s and a dictionary words, return every sentence s can be broken into, rather than merely whether one exists. Every character must be used and every piece must be a dictionary word, words may be reused any number of times, and a string with no valid break returns an empty list.

Examples

Example 1

Input
s = "catsanddog"dictionary = ["cat", "cats", "and", "sand", "dog"]
Output
["cat sand dog","cats and dog"]
cat sand dog and cats and dog: both use every character, and every piece is a word.

Example 2

Input
s = "catsandog"dictionary = ["cats", "dog", "sand", "and", "cat"]
Output
[]
Every way of starting leaves og at the end, which is not a word, so no sentence exists.

The Code

function wordBreakAll(s, dictionary) {
  const memo = {};
  function solve(start) {
    if (start === s.length) return [""];
    if (memo[start] !== undefined) return memo[start];
    const results = [];
    for (let end = start + 1; end <= s.length; end++) {
      const piece = s.slice(start, end);
      if (dictionary.indexOf(piece) === -1) continue;
      const rest = solve(end);
      for (let i = 0; i < rest.length; i++) {
        results.push(rest[i] === "" ? piece : piece + " " + rest[i]);
      }
    }
    memo[start] = results;
    return results;
  }
  return solve(0);
}
wordBreakAll("catsanddog", ["cat", "cats", "and", "sand", "dog"]);
Done

The first 31 calls, of 47. This one does not fit on a page.

Step through wordBreakAll("catsanddog", ["cat", "cats", "and", "sand", "dog"]) call by call

More like this

All dynamic programming examples (20) →