Problem

You are given a string s that contains digits 0-9, addition symbols '+', and multiplication symbols '*' only , representing a valid math expression of single digit numbers (e.g., 3+5*2). This expression was given to n elementary school students. The students were instructed to get the answer of the expression by following this order of operations :

  1. Compute multiplication , reading from left to right ; Then,
  2. Compute addition , reading from left to right.

You are given an integer array answers of length n, which are the submitted answers of the students in no particular order. You are asked to grade the answers, by following these rules :

  • If an answer equals the correct answer of the expression, this student will be rewarded 5 points;
  • Otherwise, if the answer could be interpreted as if the student applied the operators in the wrong order but had correct arithmetic , this student will be rewarded 2 points;
  • Otherwise, this student will be rewarded 0 points.

Return the sum of the points of the students.

Examples

Example 1

1
2
3
4
5
6
7
8


![](https://assets.leetcode.com/uploads/2021/09/17/student_solving_math.png)

Input: s = "7+3*1*2", answers = [20,13,42]
Output: 7
Explanation: As illustrated above, the correct answer of the expression is 13, therefore one student is rewarded 5 points: [20,_**13**_ ,42]
A student might have applied the operators in this wrong order: ((7+3)*1)*2 = 20. Therefore one student is rewarded 2 points: [_**20**_ ,13,42]
The points for the students are: [2,5,0]. The sum of the points is 2+5+0=7.

Example 2

1
2
3
4
5

Input: s = "3+5*2", answers = [13,0,10,13,13,16,16]
Output: 19
Explanation: The correct answer of the expression is 13, therefore three students are rewarded 5 points each: [**_13_** ,0,10,**_13_** ,**_13_** ,16,16]
A student might have applied the operators in this wrong order: ((3+5)*2 = 16. Therefore two students are rewarded 2 points: [13,0,10,13,13,**_16_** ,**_16_**]
The points for the students are: [5,0,0,5,5,2,2]. The sum of the points is 5+0+0+5+5+2+2=19.

Example 3

1
2
3
4
5
6

Input: s = "6+0*1", answers = [12,9,6,4,8,6]
Output: 10
Explanation: The correct answer of the expression is 6.
If a student had incorrectly done (6+0)*1, the answer would also be 6.
By the rules of grading, the students will still be rewarded 5 points (as they got the correct answer), not 2 points.
The points for the students are: [0,0,5,0,0,5]. The sum of the points is 10.

Constraints

  • 3 <= s.length <= 31
  • s represents a valid expression that contains only digits 0-9, '+', and '*' only.
  • All the integer operands in the expression are in the inclusive range [0, 9].
  • 1 <= The count of all operators ('+' and '*') in the math expression <= 15
  • Test data are generated such that the correct answer of the expression is in the range of [0, 1000].
  • n == answers.length
  • 1 <= n <= 10^4
  • 0 <= answers[i] <= 1000

Solution

Method 1 - DP for All Possible Results, Stack for Correct Answer

We use dynamic programming to compute all possible results for each subexpression (with any parenthesization), and a stack to compute the correct answer (left-to-right precedence). For each answer, award 5 points if correct, 2 if in the set of possible wrong results, 0 otherwise.

Code

 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

#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
class Solution {
public:
    int scoreOfStudents(string s, vector<int>& answers) {
        int n = (s.size() + 1) / 2;
        vector<vector<unordered_set<int>>> dp(n, vector<unordered_set<int>>(n));
        for (int i = 0; i < n; ++i) dp[i][i].insert(s[2*i] - '0');
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;
                for (int k = i; k < j; ++k) {
                    for (int a : dp[i][k]) for (int b : dp[k+1][j]) {
                        char op = s[2*k+1];
                        int val = (op == '+') ? a + b : a * b;
                        if (val <= 1000) dp[i][j].insert(val);
                    }
                }
            }
        }
        int correct = eval(s);
        int res = 0;
        for (int x : answers) {
            if (x == correct) res += 5;
            else if (dp[0][n-1].count(x)) res += 2;
        }
        return res;
    }
    int eval(const string& s) {
        vector<int> nums;
        char op = 0;
        for (char c : s) {
            if (isdigit(c)) {
                int d = c - '0';
                if (op == '*') {
                    nums.back() *= d;
                    op = 0;
                } else {
                    nums.push_back(d);
                }
            } else if (c == '+' || c == '*') {
                op = c;
            }
        }
        int sum = 0;
        for (int x : nums) sum += x;
        return sum;
    }
};
 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

import java.util.*;
class Solution {
    public int scoreOfStudents(String s, int[] answers) {
        int n = (s.length() + 1) / 2;
        Set<Integer>[][] dp = new HashSet[n][n];
        for (int i = 0; i < n; ++i) {
            dp[i][i] = new HashSet<>();
            dp[i][i].add(s.charAt(2*i) - '0');
        }
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;
                dp[i][j] = new HashSet<>();
                for (int k = i; k < j; ++k) {
                    for (int a : dp[i][k]) for (int b : dp[k+1][j]) {
                        char op = s.charAt(2*k+1);
                        int val = op == '+' ? a + b : a * b;
                        if (val <= 1000) dp[i][j].add(val);
                    }
                }
            }
        }
        int correct = eval(s);
        int res = 0;
        for (int x : answers) {
            if (x == correct) res += 5;
            else if (dp[0][n-1].contains(x)) res += 2;
        }
        return res;
    }
    private int eval(String s) {
        List<Integer> nums = new ArrayList<>();
        char op = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                int d = c - '0';
                if (op == '*') {
                    nums.set(nums.size()-1, nums.get(nums.size()-1) * d);
                    op = 0;
                } else {
                    nums.add(d);
                }
            } else if (c == '+' || c == '*') {
                op = c;
            }
        }
        int sum = 0;
        for (int x : nums) sum += x;
        return sum;
    }
}
 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

from typing import List
class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        n = (len(s) + 1) // 2
        dp = [[set() for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i].add(int(s[2*i]))
        for l in range(2, n+1):
            for i in range(n-l+1):
                j = i + l - 1
                for k in range(i, j):
                    for a in dp[i][k]:
                        for b in dp[k+1][j]:
                            op = s[2*k+1]
                            val = a + b if op == '+' else a * b
                            if val <= 1000:
                                dp[i][j].add(val)
        def eval_expr(s):
            nums = []
            op = None
            for c in s:
                if c.isdigit():
                    d = int(c)
                    if op == '*':
                        nums[-1] *= d
                        op = None
                    else:
                        nums.append(d)
                elif c in '+*':
                    op = c
            return sum(nums)
        correct = eval_expr(s)
        res = 0
        for x in answers:
            if x == correct:
                res += 5
            elif x in dp[0][n-1]:
                res += 2
        return res
 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

use std::collections::HashSet;
impl Solution {
    pub fn score_of_students(s: String, answers: Vec<i32>) -> i32 {
        let n = (s.len() + 1) / 2;
        let s = s.as_bytes();
        let mut dp = vec![vec![HashSet::new(); n]; n];
        for i in 0..n {
            dp[i][i].insert((s[2*i] - b'0') as i32);
        }
        for len in 2..=n {
            for i in 0..=n-len {
                let j = i + len - 1;
                for k in i..j {
                    for &a in &dp[i][k] {
                        for &b in &dp[k+1][j] {
                            let op = s[2*k+1] as char;
                            let val = if op == '+' { a + b } else { a * b };
                            if val <= 1000 {
                                dp[i][j].insert(val);
                            }
                        }
                    }
                }
            }
        }
        fn eval(s: &[u8]) -> i32 {
            let mut nums = vec![];
            let mut op = 0u8;
            for &c in s {
                if c.is_ascii_digit() {
                    let d = c - b'0';
                    if op == b'*' {
                        let last = nums.pop().unwrap();
                        nums.push(last * d as i32);
                        op = 0;
                    } else {
                        nums.push(d as i32);
                    }
                } else if c == b'+' || c == b'*' {
                    op = c;
                }
            }
            nums.iter().sum()
        }
        let correct = eval(s);
        let mut res = 0;
        for &x in &answers {
            if x == correct {
                res += 5;
            } else if dp[0][n-1].contains(&x) {
                res += 2;
            }
        }
        res
    }
}
 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

function scoreOfStudents(s: string, answers: number[]): number {
    const n = (s.length + 1) / 2;
    const dp: Set<number>[][] = Array.from({length: n}, () => Array.from({length: n}, () => new Set<number>()));
    for (let i = 0; i < n; ++i) dp[i][i].add(Number(s[2*i]));
    for (let l = 2; l <= n; ++l) {
        for (let i = 0; i + l - 1 < n; ++i) {
            const j = i + l - 1;
            for (let k = i; k < j; ++k) {
                for (const a of dp[i][k]) for (const b of dp[k+1][j]) {
                    const op = s[2*k+1];
                    const val = op === '+' ? a + b : a * b;
                    if (val <= 1000) dp[i][j].add(val);
                }
            }
        }
    }
    function evalExpr(s: string): number {
        const nums: number[] = [];
        let op = '';
        for (const c of s) {
            if (c >= '0' && c <= '9') {
                const d = Number(c);
                if (op === '*') {
                    nums[nums.length-1] *= d;
                    op = '';
                } else {
                    nums.push(d);
                }
            } else if (c === '+' || c === '*') {
                op = c;
            }
        }
        return nums.reduce((a, b) => a + b, 0);
    }
    const correct = evalExpr(s);
    let res = 0;
    for (const x of answers) {
        if (x === correct) res += 5;
        else if (dp[0][n-1].has(x)) res += 2;
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(L^3 + n) (L = length of s, n = number of answers)
  • 🧺 Space complexity: O(L^2)