Find All Good Strings LeetCode solution in Java

1
class Solution {
2
  Integer[][][][] dp;
3
  int mod = 1000000007;
4
  int[] lps;
5

6
  private int add(int a, int b) {
7
    return (a % mod + b % mod) % mod;
8
  }
9

10
  private int solve(
11
      char[] s1,
12
      char[] s2,
13
      int cur,
14
      boolean isStrictLower,
15
      boolean isStrictUpper,
16
      char[] evil,
17
      int evI) {
18
    if (evI == evil.length) return 0;
19
    if (cur == s2.length) return 1;
20
    if (dp[cur][isStrictLower ? 1 : 0][isStrictUpper ? 1 : 0][evI] != null)
21
      return dp[cur][isStrictLower ? 1 : 0][isStrictUpper ? 1 : 0][evI];
22
    char start = isStrictLower ? s1[cur] : 'a';
23
    char end = isStrictUpper ? s2[cur] : 'z';
24
    int res = 0;
25
    for (char ch = start; ch <= end; ch++) {
26
      if (evil[evI] == ch)
27
        res =
28
            add(
29
                res,
30
                solve(
31
                    s1,
32
                    s2,
33
                    cur + 1,
34
                    isStrictLower && ch == start,
35
                    isStrictUpper && ch == end,
36
                    evil,
37
                    evI + 1));
38
      else {
39
        int j = evI;
40
        while (j > 0 && evil[j] != ch) j = lps[j - 1];
41
        if (ch == evil[j]) j++;
42
        res =
43
            add(
44
                res,
45
                solve(
46
                    s1,
47
                    s2,
48
                    cur + 1,
49
                    isStrictLower && ch == start,
50
                    isStrictUpper && ch == end,
51
                    evil,
52
                    j));
53
      }
54
    }
55
    return dp[cur][isStrictLower ? 1 : 0][isStrictUpper ? 1 : 0][evI] = res;
56
  }
57

58
  public int findGoodStrings(int n, String s1, String s2, String evil) {
59
    char[] arr = s1.toCharArray();
60
    char[] brr = s2.toCharArray();
61
    char[] crr = evil.toCharArray();
62
    lps = new int[crr.length];
63
    for (int i = 1, j = 0; i < crr.length; i++) {
64
      while (j > 0 && crr[i] != crr[j]) j = lps[j - 1];
65
      if (crr[i] == crr[j]) lps[i] = ++j;
66
    }
67
    dp = new Integer[n][2][2][crr.length];
68
    return solve(arr, brr, 0, true, true, crr, 0);
69
  }
70
}