The Score of Students Solving Math Expression - Video Solutions
LeetCode 2019. The Score of Students Solving Math Expression
The Score of Students Solving Math Expression - Video Solution
Watch 4 video solutions for The Score of Students Solving Math Expression, a hard level problem involving Array, Math, String. This walkthrough by Happy Coding has 1,598 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- Compute multiplication, reading from left to right; Then,
- 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
5points; - 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
2points; - Otherwise, this student will be rewarded
0points.
Return the sum of the points of the students.
Example 1:
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 <= 31srepresents a valid expression that contains only digits0-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.length1 <= n <= 1040 <= answers[i] <= 1000
Approach Overview
Problem Overview: You are given a math expression containing digits, +, and *. Students submit answers after evaluating the expression, sometimes applying incorrect operator precedence. You must award 5 points for the correct answer and 2 points for answers that could appear from a valid but incorrectly parenthesized evaluation.
Approach 1: Evaluate with Left-to-Right Multiplication First (Stack Evaluation) (O(n) time, O(n) space)
First compute the correct value of the expression using normal arithmetic precedence where multiplication happens before addition. Scan the string and use a stack to handle multiplication immediately while deferring addition. When a digit is read, multiply with the top of the stack if the previous operator is *; otherwise push it. The final result is the sum of stack values. This step gives the true answer used to award 5 points and serves as the baseline for scoring.
Approach 2: Evaluate with Brackets (Alternate Total Order) using Dynamic Programming (O(n^3) time, O(n^2) space)
Students who ignore operator precedence effectively evaluate the expression using arbitrary parenthesization. Model this with interval dynamic programming. Let dp[i][j] store all possible values produced from the substring between numbers i and j. For every operator position k, combine results from dp[i][k] and dp[k+1][j] using the operator. Use memoization to avoid recomputing intervals and keep only results ≤1000 as required by the problem constraints. This generates the complete set of answers a student could produce when evaluating the expression incorrectly.
After computing both values, iterate through the students' answers array. If an answer equals the correct evaluation, add 5. If it exists in the DP-generated set of possible incorrect results, add 2. Otherwise add 0. The DP essentially enumerates every possible evaluation tree of the expression using techniques common in stack and expression parsing problems.
Recommended for interviews: Interviewers expect the dynamic programming interval solution combined with correct expression evaluation. The stack-based evaluation shows you understand operator precedence, while the DP demonstrates deeper algorithmic reasoning about expression trees and subproblem reuse.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack Evaluation for Correct Result | O(n) | O(n) | Compute the true expression value with standard precedence |
| Interval Dynamic Programming (All Parenthesizations) | O(n^3) | O(n^2) | Generate all valid results from incorrect evaluation orders |
| Memoized Recursive Expression Evaluation | O(n^3) | O(n^2) | Cleaner implementation of the same interval DP idea |