# The Score of Students Solving Math Expression
**Difficulty:** HARD
[External](https://leetcode.com/problems/the-score-of-students-solving-math-expression)
Canonical: https://scaleengineer.com/dsa/problems/the-score-of-students-solving-math-expression
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Data structures:** Array, String, Stack
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart)
---
## 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_.

**Example 1:**

![](https://assets.glich.co/dsa/the-score-of-students-solving-math-expression/image0.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:**

**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:**

**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 <= 104`
* `0 <= answers[i] <= 1000`

# Approaches
## Brute-force Recursion
This approach uses simple recursion to find all possible outcomes of the mathematical expression. It explores every possible way to evaluate the expression by splitting it at each operator and recursively solving the sub-expressions. This method correctly identifies all possible values a student could get by applying operators in any order, but it's highly inefficient.
**Time:** Exponential, roughly O(C_k), where k is the number of operators and C_k is the k-th Catalan number. This is because it explores all possible parenthesizations of the expression without storing intermediate results. · **Space:** O(C_k * L), where k is the number of operators and L is the length of the expression. The recursion depth can be large, and sets of results are created at each call. The number of evaluation paths is related to Catalan numbers (C_k), leading to exponential space usage.
**Pros:** Conceptually simple and a direct translation of the problem statement for finding all possible answers.
**Cons:** Extremely inefficient due to re-computation of results for the same sub-expressions.; Will result in a 'Time Limit Exceeded' error for all but the smallest inputs.
### Explanation
The core idea is to define a recursive function that takes a sub-expression as input and returns a set of all possible values it can evaluate to. This is achieved by trying every operator as the last one to be evaluated.

For an expression like `a+b*c`, the function would try splitting at `+` and `*`:
1.  Split at `+`: `(a) + (b*c)`. Recursively find all values for `a` (which is just `{a}`) and `b*c`. Then combine them.
2.  Split at `*`: `(a+b) * (c)`. Recursively find all values for `a+b` and `c`. Then combine them.

This process continues until the sub-expressions are single numbers. The main drawback is that the function will re-calculate results for the same sub-expression multiple times. For example, in evaluating `(a+b*c)+d`, the results for `a+b*c` would be computed independently, without recognizing that `b*c` might have been computed as part of another sub-problem.

```java
class Solution {
    private List<Integer> nums;
    private List<Character> ops;

    public int scoreOfStudents(String s, int[] answers) {
        nums = new ArrayList<>();
        ops = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                nums.add(c - '0');
            } else {
                ops.add(c);
            }
        }

        int correctAnswer = calculateCorrect(s);
        Set<Integer> allPossibleAnswers = calculateAll(0, nums.size() - 1);

        int totalScore = 0;
        for (int ans : answers) {
            if (ans == correctAnswer) {
                totalScore += 5;
            } else if (allPossibleAnswers.contains(ans)) {
                totalScore += 2;
            }
        }
        return totalScore;
    }

    private int calculateCorrect(String s) {
        String[] addParts = s.split("\\+");
        int result = 0;
        for (String term : addParts) {
            String[] mulParts = term.split("\\*");
            int product = 1;
            for (String factor : mulParts) {
                product *= Integer.parseInt(factor);
            }
            result += product;
        }
        return result;
    }

    private Set<Integer> calculateAll(int i, int j) {
        Set<Integer> res = new HashSet<>();
        if (i == j) {
            res.add(nums.get(i));
            return res;
        }

        for (int k = i; k < j; k++) {
            Set<Integer> leftResults = calculateAll(i, k);
            Set<Integer> rightResults = calculateAll(k + 1, j);
            char op = ops.get(k);

            for (int leftVal : leftResults) {
                for (int rightVal : rightResults) {
                    int currentVal = (op == '+') ? (leftVal + rightVal) : (leftVal * rightVal);
                    if (currentVal <= 1000) {
                        res.add(currentVal);
                    }
                }
            }
        }
        return res;
    }
}
```
### Algorithm
- Define a recursive function, let's call it `calculateAll(subExpression)`, which will return a set of all possible integer results for a given `subExpression` string.
- The base case for the recursion is when the `subExpression` is just a single number. In this case, the function returns a set containing that number.
- For the recursive step, iterate through the `subExpression` to find all operators. For each operator found, split the expression into a `left` part and a `right` part.
- Make two recursive calls: `calculateAll(left)` and `calculateAll(right)` to get the sets of possible results for each part.
- Combine the results from the left and right sets. For each pair of values `(l, r)` from the left and right sets, compute `l + r` or `l * r` based on the operator. Add the new value to the result set for the current `subExpression` if it's less than or equal to 1000.
- To get the final score, first calculate the correct answer using standard operator precedence (multiplication before addition). Then, call `calculateAll(s)` for the original string `s` to get all possible answers from incorrect evaluation orders.
- Iterate through each student's answer, awarding 5 points if it matches the correct answer, 2 points if it's in the set of possible answers (and not the correct one), and 0 otherwise.

## Dynamic Programming with Memoization
This approach significantly optimizes the brute-force recursion by using dynamic programming with memoization. The key insight is that the brute-force method repeatedly calculates the possible values for the same sub-expressions. By storing the results of these sub-problems in a memoization table (e.g., a 2D array), we can look them up instead of re-computing them, drastically reducing the computation time. The problem's constraint that student answers are at most 1000 allows for effective pruning of the search space, making this approach feasible.
**Time:** O(M^3 * S^2), where M is the number of operands and S is the maximum size of the result set. There are O(M^2) states, each takes O(M) transitions. Each transition involves iterating through two sets of size up to S. The pruning based on the value limit (<= 1000) makes the practical performance much better than this worst-case bound suggests. · **Space:** O(M^2 * S), where M is the number of operands (at most 16) and S is the maximum size of the result set for any sub-expression (at most 1001). This is for the memoization table.
**Pros:** Efficient enough to solve the problem within the given time limits.; Systematically explores all possibilities without redundant work.; The pruning step (values <= 1000) makes it very effective for the given constraints.
**Cons:** More complex to implement compared to the brute-force recursive approach.; Requires additional space for the memoization table, proportional to the square of the number of operands.
### Explanation
The overall strategy involves three main steps: calculating the correct answer, calculating all possible answers, and then grading.

1.  **Correct Answer**: The specified order of operations (multiplication then addition) can be handled easily. We can split the expression string by the `+` operator. This gives us terms that need to be added together. Each of these terms is an expression containing only numbers and `*` operators. We evaluate each term by multiplying its constituent numbers and then sum up the results of all terms.

2.  **All Possible Answers**: This is the core of the DP approach. We define a function `dp(i, j)` that returns a set of all possible values for the sub-expression starting at the i-th number and ending at the j-th number. 
    - We use a `Set<Integer>[][] memo` table to store results. Before computing `dp(i, j)`, we check if `memo[i][j]` already has the result.
    - The function iterates through all operators between `i` and `j` to serve as the final operation. For an operator at index `k`, we combine results from `dp(i, k)` and `dp(k+1, j)`.
    - A critical optimization is to only store results that are `<= 1000`, since any larger value cannot match a student's answer.

3.  **Grading**: With the correct answer and the set of all possible answers, we can iterate through the students' submissions and assign points according to the rules.

```java
class Solution {
    private Set<Integer>[][] memo;
    private List<Integer> nums;
    private List<Character> ops;

    public int scoreOfStudents(String s, int[] answers) {
        nums = new ArrayList<>();
        ops = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                nums.add(c - '0');
            } else {
                ops.add(c);
            }
        }

        int correctAnswer = calculateCorrect(s);

        int n = nums.size();
        memo = new HashSet[n][n];
        Set<Integer> allPossibleAnswers = dp(0, n - 1);

        int totalScore = 0;
        for (int ans : answers) {
            if (ans == correctAnswer) {
                totalScore += 5;
            } else if (allPossibleAnswers.contains(ans)) {
                totalScore += 2;
            }
        }
        return totalScore;
    }

    private int calculateCorrect(String s) {
        String[] addParts = s.split("\\+");
        int result = 0;
        for (String term : addParts) {
            String[] mulParts = term.split("\\*");
            int product = 1;
            for (String factor : mulParts) {
                product *= Integer.parseInt(factor);
            }
            result += product;
        }
        return result;
    }

    private Set<Integer> dp(int i, int j) {
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        Set<Integer> res = new HashSet<>();
        if (i == j) {
            res.add(nums.get(i));
            memo[i][j] = res;
            return res;
        }

        for (int k = i; k < j; k++) {
            Set<Integer> leftResults = dp(i, k);
            Set<Integer> rightResults = dp(k + 1, j);
            char op = ops.get(k);

            for (int leftVal : leftResults) {
                for (int rightVal : rightResults) {
                    int currentVal = (op == '+') ? (leftVal + rightVal) : (leftVal * rightVal);
                    if (currentVal <= 1000) {
                        res.add(currentVal);
                    }
                }
            }
        }
        memo[i][j] = res;
        return res;
    }
}
```
### Algorithm
- First, parse the input string `s` into a list of numbers (`nums`) and a list of operators (`ops`).
- Calculate the correct answer by evaluating multiplications first, then additions. A simple way is to split the string by `+`, evaluate each resulting term (which only contains `*`), and then sum up the results.
- To find all possible answers from incorrect evaluation orders, use dynamic programming with memoization. Create a 2D array, `memo`, where `memo[i][j]` will store the set of all possible results for the sub-expression from `nums[i]` to `nums[j]`.
- Implement a recursive helper function, `dp(i, j)`, that computes these sets.
- The base case for `dp(i, j)` is when `i == j`, where the result is just the number `nums[i]`.
- In the recursive step, iterate through all possible split points `k` from `i` to `j-1`. For each split, recursively call `dp(i, k)` and `dp(k+1, j)` to get results for the left and right sub-expressions.
- Combine the results from left and right sets using the operator `ops[k]`. Crucially, only add results that are less than or equal to 1000 to the set for `(i, j)`, as any larger value is irrelevant.
- Store the computed set in `memo[i][j]` to avoid re-computation.
- After computing the correct answer and the set of all possible answers, iterate through the `answers` array and tally the total score based on the grading rules.

# Solutions
### Java

```java
class Solution { public int scoreOfStudents ( String s , int [] answers ) { int n = s . length (); int x = cal ( s ); int m = ( n + 1 ) >> 1 ; Set < Integer >[][] f = new Set [ m ][ m ]; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < m ; ++ j ) { f [ i ][ j ] = new HashSet <>(); } f [ i ][ i ]. add ( s . charAt ( i << 1 ) - '0' ); } for ( int i = m - 1 ; i >= 0 ; -- i ) { for ( int j = i ; j < m ; ++ j ) { for ( int k = i ; k < j ; ++ k ) { for ( int l : f [ i ][ k ]) { for ( int r : f [ k + 1 ][ j ]) { char op = s . charAt ( k << 1 | 1 ); if ( op == '+' && l + r <= 1000 ) { f [ i ][ j ]. add ( l + r ); } else if ( op == '*' && l * r <= 1000 ) { f [ i ][ j ]. add ( l * r ); } } } } } } int [] cnt = new int [ 1001 ]; for ( int ans : answers ) { ++ cnt [ ans ]; } int ans = 5 * cnt [ x ]; for ( int i = 0 ; i <= 1000 ; ++ i ) { if ( i != x && f [ 0 ][ m - 1 ]. contains ( i )) { ans += 2 * cnt [ i ]; } } return ans ; } private int cal ( String s ) { int res = 0 , pre = s . charAt ( 0 ) - '0' ; for ( int i = 1 ; i < s . length (); i += 2 ) { char op = s . charAt ( i ); int cur = s . charAt ( i + 1 ) - '0' ; if ( op == '*' ) { pre *= cur ; } else { res += pre ; pre = cur ; } } res += pre ; return res ; } }
```

### CPP

```cpp
class Solution {
public:
  int scoreOfStudents(string s, vector<int> &answers) {
    int n = s.size();
    int x = cal(s);
    int m = (n + 1) >> 1;
    unordered_set<int> f[m][m];
    for (int i = 0; i < m; ++i) {
      f[i][i] = {s[i * 2] - '0'};
    }
    for (int i = m - 1; ~i; --i) {
      for (int j = i; j < m; ++j) {
        for (int k = i; k < j; ++k) {
          for (int l : f[i][k]) {
            for (int r : f[k + 1][j]) {
              char op = s[k << 1 | 1];
              if (op == '+' && l + r <= 1000) {
                f[i][j].insert(l + r);
              } else if (op == '*' && l * r <= 1000) {
                f[i][j].insert(l * r);
              }
            }
          }
        }
      }
    }
    int cnt[1001]{};
    for (int t : answers) {
      ++cnt[t];
    }
    int ans = 5 * cnt[x];
    for (int i = 0; i <= 1000; ++i) {
      if (i != x && f[0][m - 1].count(i)) {
        ans += cnt[i] << 1;
      }
    }
    return ans;
  }
  int cal(string &s) {
    int res = 0;
    int pre = s[0] - '0';
    for (int i = 1; i < s.size(); i += 2) {
      int cur = s[i + 1] - '0';
      if (s[i] == '*') {
        pre *= cur;
      } else {
        res += pre;
        pre = cur;
      }
    }
    res += pre;
    return res;
  }
};

```

### Python

```python
class Solution : def scoreOfStudents ( self , s : str , answers : List [ int ]) -> int : def cal ( s : str ) -> int : res , pre = 0 , int ( s [ 0 ]) for i in range ( 1 , n , 2 ): if s [ i ] == "*" : pre *= int ( s [ i + 1 ]) else : res += pre pre = int ( s [ i + 1 ]) res += pre return res n = len ( s ) x = cal ( s ) m = ( n + 1 ) >> 1 f = [[ set () for _ in range ( m )] for _ in range ( m )] for i in range ( m ): f [ i ][ i ] = { int ( s [ i << 1 ])} for i in range ( m - 1 , - 1 , - 1 ): for j in range ( i , m ): for k in range ( i , j ): for l in f [ i ][ k ]: for r in f [ k + 1 ][ j ]: if s [ k << 1 | 1 ] == "+" and l + r <= 1000 : f [ i ][ j ]. add ( l + r ) elif s [ k << 1 | 1 ] == "*" and l * r <= 1000 : f [ i ][ j ]. add ( l * r ) cnt = Counter ( answers ) ans = cnt [ x ] * 5 for k , v in cnt . items (): if k != x and k in f [ 0 ][ m - 1 ]: ans += v << 1 return ans
```