countconstructtabulative.js

const countConstruct = (target, wordBank) => {
  const table = new Array(target.length + 1).fill(0);
  table[0] = 1;
  for (let i = 0; i <= target.length; i += 1) {
    if (!table[i]) continue;
    const rest = target.slice(i);
    for (let word of wordBank) {
        if (!rest.startsWith(word)) continue;
        const spacesAhead = word.length;
        table[i + spacesAhead] += table[i];
    }
  }
  return table[target.length];
};
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("eeeeeeee", ["e", "ee", 'eee', 'eeee']));