【Leetcode】2019. The Score of Students Solving Math Expression

https://leetcode.com/problems/the-score-of-students-solving-math-expression/

给定一个只含数字、加号和乘号的数学表达式 s s s，每个运算数都是个位数。再给定若干学生的运算答案 A A A，如果答案恰好就是 s s s的正确结果，该学生得 5 5 5分；若将 s s s通过某种加括号的方式可以算出某个答案，则该答案记 2 2 2分；否则记 0 0 0分。求所有学生总分。题目保证正确答案以及每个学生的答案都在 [ 0 , 1000 ] [0,1000] [0,1000]。

思路是记忆化搜索。先求一下正确答案，然后开始算可能得到的答案。枚举运算符，然后递归求解两边可能的答案，汇总成当前表达式可能得到的答案。可以用记忆化的方式避免重复计算。代码如下：

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public int scoreOfStudents(String s, int[] answers) {
        int a = compute(s), res = 0, len = s.length();
        Set[][] f = new Set[len][len];
        dfs(s, 0, len - 1, f);
        Set set = f[0][len - 1];
        for (int x : answers) {
            if (a == x) {
                res += 5;
            } else if (set.contains(x)) {
                res += 2;
            }
        }
        
        return res;
    }
    
    Set dfs(String s, int l, int r, Set[][] f) {
    	// 有记忆则调取记忆
        if (f[l][r] != null) {
            return f[l][r];
        }
        
        f[l][r] = new HashSet<>();
        if (l == r) {
            f[l][r].add(s.charAt(l) - '0');
        } else {
            for (int i = l + 1; i < r; i++) {
                if (!Character.isDigit(s.charAt(i))) {
                	// 递归求解左右两边可能算出的答案
                    for (int x : dfs(s, l, i - 1, f)) {
                        for (int y : dfs(s, i + 1, r, f)) {
                            int res = 0;
                            if (s.charAt(i) == '+') {
                                res = x + y;
                            } else {
                                res = x * y;
                            }
                            
                            // 出界了的答案直接不计入
                            if (0 <= res && res <= 1000) {
                                f[l][r].add(res);
                            }
                        }
                    }
                }
            }
        }
        
        return f[l][r];
    }
    
    int compute(String s) {
        Deque stk = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                if (i > 0 && s.charAt(i - 1) == '*') {
                    stk.push(stk.pop() * (ch - '0'));
                } else {
                    stk.push(ch - '0');
                }
            }
        }
        
        int res = 0;
        while (!stk.isEmpty()) {
            res += stk.pop();
        }
        
        return res;
    }
}

时间复杂度 O ( l s 3 + l A ) O(l_s^3+l_A) O(ls3​+lA​)，空间 O ( l s 2 ) O(l_s^2) O(ls2​)。注意有 1000 1000 1000这个限制，上面所说的复杂度的常数是 100 0 2 1000^2 10002，是很大的。