Numbers At Most N Given Digit Set LeetCode solution in Java

1
class Solution {
2

3
  // DIGIT DP IS LOVE
4
  Integer[][][] digitdp;
5

6
  public int solve(String num, int pos, boolean bound, Integer[] dig, boolean lead) {
7

8
    if (pos == num.length()) {
9
      return 1;
10
    }
11

12
    int maxDigit = -1;
13

14
    if (digitdp[pos][(bound == true) ? 1 : 0][(lead == true) ? 1 : 0] != null)
15
      return digitdp[pos][(bound == true) ? 1 : 0][(lead == true) ? 1 : 0];
16

17
    if (bound) {
18
      maxDigit = num.charAt(pos) - '0';
19
    } else {
20
      maxDigit = 9;
21
    }
22

23
    int ans = 0;
24
    for (int i = 0; i <= maxDigit; i++) {
25

26
      // 0 can only be leading
27
      if (i == 0 && lead) {
28

29
        ans += solve(num, pos + 1, false, dig, lead);
30

31
      } else {
32

33
        int res = Arrays.binarySearch(dig, i);
34

35
        if (res >= 0) {
36
          // lead = false; // now it is not possible to 0 to be in lead any more once any other call
37
          // has been made
38
          ans += solve(num, pos + 1, bound & (i == num.charAt(pos) - '0'), dig, false);
39
        }
40
      }
41
    }
42

43
    return digitdp[pos][(bound == true) ? 1 : 0][(lead == true) ? 1 : 0] = ans;
44
  }
45

46
  public int atMostNGivenDigitSet(String[] digits, int n) {
47

48
    String num = n + "";
49
    Integer[] dig = new Integer[digits.length];
50
    for (int i = 0; i < dig.length; i++) {
51
      dig[i] = Integer.parseInt(digits[i]);
52
    }
53

54
    digitdp = new Integer[20][2][2];
55
    return solve(num, 0, true, dig, true) - 1;
56
  }
57
}