Find All Good Strings LeetCode solution in JavaScript

1
const mod = 10 ** 9 + 7;
2

3
let cache = null;
4

5
/**
6
 * @param {number} n
7
 * @param {string} s1
8
 * @param {string} s2
9
 * @param {string} evil
10
 * @return {number}
11
 */
12
var findGoodStrings = function (n, s1, s2, evil) {
13
  /**
14
   * 17 bits
15
   * - 9 bit: 2 ** 9 > 500 by evil
16
   * - 6 bit: 2 ** 6 > 50 by evil
17
   * - 1 bit left (bound)
18
   * - 1 bit right (bound)
19
   *
20
   * cache: `mainTraver` is the prefix length, `evilMatch` is matching for evil
21
   *
22
   * answer: marnTravel 0, evil 0, s prefix has the last character
23
   */
24
  cache = new Array(1 << 17).fill(-1);
25
  return dfs(0, 0, n, s1, s2, evil, true, true, computeNext(evil));
26
};
27
/**
28
 * DFS:
29
 * 1. loop from `s1` to `s2`, range of position `i` is [0, n]: 0 means no start, n means complete
30
 * 2. if `s1` has traversed to nth, it means has been generated a legal character, and return 1; else
31
 * 3. `mainTravel` is the length of the `s` generated by dfs last time
32
 * 4. `evilMatch` is the length that matches the last generated `s` in evilMatch evil
33
 * 5. n, s1, s2, evil, left, right, next
34
 */
35
function dfs(
36
  mainTravel,
37
  evilMatch,
38
  n,
39
  s1,
40
  s2,
41
  evil,
42
  left,
43
  right,
44
  next,
45
  ans = 0
46
) {
47
  // same length means that the match has been successful
48
  if (evilMatch === evil.length) {
49
    return 0;
50
  }
51
  // this means s is conformed
52
  if (mainTravel === n) {
53
    return 1;
54
  }
55

56
  // get key for cache
57
  let key = generateKey(mainTravel, evilMatch, left, right);
58
  // because any combination of the four categories will only appear once, there will be no repetition
59
  if (cache[key] !== -1) {
60
    return cache[key];
61
  }
62

63
  // get start, end calculate
64
  let [start, end] = [
65
    left ? s1.charCodeAt(mainTravel) : 97,
66
    right ? s2.charCodeAt(mainTravel) : 122,
67
  ];
68

69
  // loop
70
  for (let i = start; i <= end; i++) {
71
    // get char code
72
    let code = String.fromCharCode(i);
73
    // actually, `evilMatch` will only get longer or stay the same, not shorter
74
    let m = evilMatch;
75

76
    while (m > 0 && evil[m] !== code) {
77
      m = next[m - 1];
78
    }
79

80
    if (evil[m] === code) {
81
      m++;
82
    }
83

84
    // recursive
85
    ans += dfs(
86
      mainTravel + 1,
87
      m,
88
      n,
89
      s1,
90
      s2,
91
      evil,
92
      left && i === start,
93
      right && i === end,
94
      next
95
    );
96

97
    // too large
98
    ans %= mod;
99
  }
100

101
  // result after cache set
102
  return (cache[key] = ans), ans;
103
}
104

105
// create key for cache
106
function generateKey(mainTravel, evilMatch, left, right) {
107
  return (
108
    (mainTravel << 8) |
109
    (evilMatch << 2) |
110
    ((left ? 1 : 0) << 1) |
111
    (right ? 1 : 0)
112
  );
113
}
114

115
// for next right move, index + 1
116
function computeNext(evil, n = evil.length, ans = new Array(n).fill(0), k = 0) {
117
  for (let i = 1; i < n; i++) {
118
    while (k > 0 && evil[i] !== evil[k]) {
119
      k = ans[k - 1];
120
    }
121

122
    if (evil[i] === evil[k]) {
123
      ans[i] = ++k;
124
    }
125
  }
126
  return ans;
127
}