canconstructtabulative.js

const canConstruct = (target, wordBank) => {
  const table = new Array(target.length + 1).fill(false);
  // for each index of table, looking at that index
  // will be looking at the substring up to but not including that value
  // 0 would be true
  table[0] = true;
  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] = true;
      }
  }
  // O(w * W * len(target)), where W is len of longest word in wordbank
  return table[target.length]
};
console.time();
console.log(canConstruct("abcdef", ["ab", "abc", "cd", "def", "abcd"])); // -> true(abc, def)
console.log(canConstruct("skateboard", ["sk", "kat", "board", "boar", "s", "z", "d", "l", "k", "4", "54"])); // -> false
console.log(canConstruct("whatwhatwhatarearewhatamong rubble", ["what", "What ", "are", "are ", "we", "we ", "among ", "rubble"])); // -> true
console.log(canConstruct("eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeg", ["e", "ee", 'eee', 'eeee']));
console.timeEnd();