allconstructtabulative.js

const allConstruct = (target, wordBank) => {
  const table = new Array(target.length + 1)
  .fill().map(() => []);
  table[0] = [[]];
  for (let i = 0; i <= target.length; i += 1) {
      const oldCombinations = table[i];
      if (oldCombinations.length === 0) continue;
      const rest = target.slice(i);
      for (let word of wordBank) {
        if (!rest.startsWith(word)) continue;
        const lengthAdded = word.length;
        const newCombinations = table[i + lengthAdded];
        for (let currentArr of oldCombinations) {
          newCombinations.push([...currentArr, word]);
        }
      }
  }
  return table[target.length];
};
console.time();
console.log(allConstruct("dog", ["a", "b", "c", "d", "o", "g"]));
console.log(allConstruct("whatwhatwhatarearewhatamong rubble", ["what", "What ", "are", "are ", "we", "we ", "among ", "rubble"]));
console.log(allConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"]));
console.log(allConstruct("manhotdog", ["man", "hot", "dog", "manh", "ot", "d", "o", "g"]));
console.log(allConstruct("eeeeeeeeeeeeeeeeep", ["e", "ee", 'eee', 'eeee']));
console.timeEnd();