# 2019. The Score of Students Solving Math Expression

• Time: $O(|\texttt{s}|^5 + n)$
• Space: $O(|\texttt{s}|^3 + n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 class Solution { public: int scoreOfStudents(string s, vector& answers) { const int n = s.length() / 2 + 1; const unordered_map> func{ {'+', plus()}, {'*', multiplies()}}; int ans = 0; vector>> dp(n, vector>(n)); unordered_map count; for (int i = 0; i < n; ++i) dp[i][i].insert(s[i * 2] - '0'); for (int d = 1; d < n; ++d) for (int i = 0; i + d < n; ++i) { const int j = i + d; for (int k = i; k < j; ++k) { const char op = s[k * 2 + 1]; for (const int a : dp[i][k]) for (const int b : dp[k + 1][j]) { const int res = func.at(op)(a, b); if (res <= 1000) dp[i][j].insert(res); } } } const int correctAnswer = eval(s); for (const int answer : answers) ++count[answer]; for (const auto& [answer, freq] : count) if (answer == correctAnswer) ans += 5 * freq; else if (dp[0][n - 1].count(answer)) ans += 2 * freq; return ans; } private: int eval(const string& s) { int ans = 0; int prevNum = 0; int currNum = 0; char op = '+'; for (int i = 0; i < s.length(); ++i) { const char c = s[i]; if (isdigit(c)) currNum = currNum * 10 + (c - '0'); if (!isdigit(c) || i == s.length() - 1) { if (op == '+') { ans += prevNum; prevNum = currNum; } else if (op == '*') { prevNum = prevNum * currNum; } op = c; currNum = 0; } } return ans + prevNum; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 class Solution { public int scoreOfStudents(String s, int[] answers) { final int n = s.length() / 2 + 1; int ans = 0; Set[][] dp = new Set[n][n]; Map count = new HashMap<>(); for (int i = 0; i < n; ++i) for (int j = i; j < n; ++j) dp[i][j] = new HashSet<>(); for (int i = 0; i < n; ++i) dp[i][i].add(s.charAt(i * 2) - '0'); for (int d = 1; d < n; ++d) for (int i = 0; i + d < n; ++i) { final int j = i + d; for (int k = i; k < j; ++k) { final char op = s.charAt(k * 2 + 1); for (final int a : dp[i][k]) for (final int b : dp[k + 1][j]) { final int res = func(op, a, b); if (res <= 1000) dp[i][j].add(res); } } } final int correctAnswer = eval(s); for (final int answer : answers) count.merge(answer, 1, Integer::sum); for (final int answer : count.keySet()) if (answer == correctAnswer) ans += 5 * count.get(answer); else if (dp[0][n - 1].contains(answer)) ans += 2 * count.get(answer); return ans; } private int eval(final String s) { int ans = 0; int currNum = 0; int prevNum = 0; char op = '+'; for (int i = 0; i < s.length(); ++i) { final char c = s.charAt(i); if (Character.isDigit(c)) currNum = currNum * 10 + (c - '0'); if (!Character.isDigit(c) || i == s.length() - 1) { if (op == '+') { ans += prevNum; prevNum = currNum; } else if (op == '*') { prevNum = prevNum * currNum; } op = c; currNum = 0; } } return ans + prevNum; } private int func(char op, int a, int b) { if (op == '+') return a + b; return a * b; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution: def scoreOfStudents(self, s: str, answers: List[int]) -> int: n = len(s) // 2 + 1 ans = 0 func = {'+': operator.add, '*': operator.mul} dp = [[set() for j in range(n)] for _ in range(n)] for i in range(n): dp[i][i].add(int(s[i * 2])) for d in range(1, n): for i in range(n - d): j = i + d for k in range(i, j): op = s[k * 2 + 1] for a in dp[i][k]: for b in dp[k + 1][j]: res = func[op](a, b) if res <= 1000: dp[i][j].add(res) correctAnswer = eval(s) for answer, freq in collections.Counter(answers).items(): if answer == correctAnswer: ans += 5 * freq elif answer in dp[0][n - 1]: ans += 2 * freq return ans