1
class Solution {
2
  public int scoreOfStudents(String s, int[] answers) {
3
    BitSet[][] ok = new BitSet[32][32];
4
    solve(0, s.length() - 1, s, ok);
5
    int ans = 0, correct = eval(s);
6
    for (int n : answers) {
7
      if (correct == n) {
8
        ans += 5;
9
      } else if (ok[0][s.length() - 1].get(n)) {
10
        ans += 2;
11
      }
12
    }
13
    return ans;
14
  }
15

16
  private BitSet solve(int lo, int hi, String s, BitSet[][] memo) {
17
    if (memo[lo][hi] != null) { // memo
18
      return memo[lo][hi];
19
    }
20
    BitSet cur = new BitSet();
21
    if (lo == hi) { // base case -> number itself [0 - 9]
22
      cur.set(s.charAt(lo) - '0');
23
      return memo[lo][hi] = cur;
24
    }
25
    for (int i = lo; i <= hi; i++) {
26
      if (s.charAt(i) == '+' || s.charAt(i) == '*') {
27
        BitSet l = solve(lo, i - 1, s, memo); // left
28
        BitSet r = solve(i + 1, hi, s, memo); // right
29
        for (int j = l.nextSetBit(0); j >= 0; j = l.nextSetBit(j + 1)) {
30
          for (int k = r.nextSetBit(0); k >= 0; k = r.nextSetBit(k + 1)) {
31
            int val = s.charAt(i) == '+' ? j + k : j * k;
32
            if (val > 1000) {
33
              break;
34
            }
35
            cur.set(val);
36
          }
37
        }
38
      }
39
    }
40
    return memo[lo][hi] = cur;
41
  }
42

43
  private int eval(String s) {
44
    Deque<Integer> stack = new ArrayDeque<>();
45
    Deque<Character> op = new ArrayDeque<>();
46
    for (char ch : s.toCharArray()) {
47
      if (ch == '+' || ch == '*') {
48
        while (!op.isEmpty() && (ch == '+' || op.peek() == '*')) {
49
          char w = op.pop();
50
          int r = stack.pop(), l = stack.pop();
51
          stack.push(w == '+' ? l + r : l * r);
52
        }
53
        op.push(ch);
54
      } else {
55
        stack.push(ch - '0');
56
      }
57
    }
58
    while (!op.isEmpty()) {
59
      char w = op.pop();
60
      int r = stack.pop(), l = stack.pop();
61
      stack.push(w == '+' ? l + r : l * r);
62
    }
63

64
    return stack.pop();
65
  }
66
}