Number of Ways to Form a Target String Given a Dictionary LeetCode solution in JavaScript

1
/**
2
 * @param {string[]} words
3
 * @param {string} target
4
 * @return {number}
5
 */
6
var numWays = function (words, target) {
7
  const targetLength = target.length;
8
  const wordsLength = words.length;
9
  const wordLength = words[0].length;
10
  const mem = Array(targetLength)
11
    .fill(0)
12
    .map(() => Array(targetLength));
13

14
  const count = Array(26)
15
    .fill(0)
16
    .map(() => ({}));
17
  for (let i = 0; i < wordsLength; i++) {
18
    for (let j = 0; j < wordLength; j++) {
19
      if (!count[words[i].charCodeAt(j) - 97][j]) {
20
        count[words[i].charCodeAt(j) - 97][j] = 0;
21
      }
22
      count[words[i].charCodeAt(j) - 97][j]++;
23
    }
24
  }
25

26
  const dp = (targetIndex, minIndex) => {
27
    if (targetIndex === targetLength) {
28
      return 1;
29
    }
30
    if (wordLength - minIndex < targetLength - targetIndex) return 0;
31
    if (mem[targetIndex][minIndex] !== undefined)
32
      return mem[targetIndex][minIndex];
33
    let res = 0;
34

35
    for (let i = minIndex; i < wordLength; i++) {
36
      if (count[target.charCodeAt(targetIndex) - 97][i]) {
37
        res +=
38
          Number(count[target.charCodeAt(targetIndex) - 97][i]) *
39
          dp(targetIndex + 1, i + 1);
40
      }
41
    }
42

43
    res %= 1e9 + 7;
44
    mem[targetIndex][minIndex] = res;
45
    return res;
46
  };
47

48
  return dp(0, 0);
49
};