allconstruct.js

const allConstruct = (target, wordBank, memo = new Map()) => {
  if (memo.has(target)) return memo.get(target);
  if (target.length === 0) return [[]];
  const res = [];
  for (let word of wordBank) {
    if (!target.startsWith(word)) continue;
    const remainder = target.slice(word.length);
    const partialArr = allConstruct(remainder, wordBank, memo).map((arr) => [word, ...arr]);
    res.push(...partialArr);
  }
  memo.set(target, [...res]);
  return memo.get(target);
  // return [...res];
};
console.time();
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("eeeeeeeeeeeeeeeee", ["e", "ee", 'eee', 'eeee']));
console.timeEnd();