countconstruct.js

const countConstruct = (target, wordbank, memo = new Map()) => {
  if (memo.has(target)) return memo.get(target);
  if (target.length === 0) return 0;
  let ways = 0;
  for(let word of wordbank) {
      if (!target.startsWith(word)) continue;
      const remainder = target.slice(word.length);
      if (remainder.length === 0) ways += 1;
      const waysRecursive = countConstruct(remainder, wordbank, memo);
      ways += waysRecursive;
  }
  memo.set(target, ways);
  return ways;
};
console.log(countConstruct("whatwhatwhatarearewhatamong rubble", ["what", "What ", "are", "are ", "we", "we ", "among ", "rubble"]));
console.log(countConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"]));
console.log(countConstruct("manhotdog", ["man", "hot", "dog", "manh", "ot", "d", "o", "g"]));
console.log(countConstruct("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee", ["e", "ee", 'eee', 'eeee']));