#2019

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

The Score of Students Solving Math Expression

Calculate student scores for a single-digit math expression using state transition dynamic programming to track all valid outcomes efficiently.

array math string dynamic programming stack

Problem Statement

You are given a string s containing digits '0'-'9' and operators '+' and '*' representing a valid single-digit math expression. Each student computes this expression and submits an answer following standard operator precedence rules.

Given an integer array answers of length n representing each student's submission, calculate the total points. Award 5 points for correct answers and 2 points for answers that are possible with an alternative order of operations. Return the sum of all students' points.

Examples

Example 1

Input: s = "7+3*1*2", answers = [20,13,42]

Output: 7

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

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

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

Solution Approach

Parse Expression and Initialize DP Table

Split the input string into numbers and operators. Use a DP table or memoization dictionary where dp[i][j] stores all possible values for the subexpression from index i to j. This allows capturing every valid state transition of the expression.

Recursive Computation with Memoization

Define a recursive function to compute all possible results for each subexpression. For each operator between i and j, combine all left and right subresults according to the operator. Cache results in the DP table to avoid redundant calculations and ensure efficiency.

Score Calculation

Compare each student's answer to the set of all computed results. Assign 5 points for the exact correct result and 2 points for any other valid evaluation. Sum the points across all students and return the total.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(4^k * n) where k is the number of operators, due to generating all possible subexpression evaluations. Space complexity is O(k^2) for memoization storage of subexpression results.

What Interviewers Usually Probe

Are you considering operator precedence and all alternative evaluation orders?
How are you memoizing intermediate results to prevent recomputation?
Can you handle overlapping subexpressions efficiently using DP?

Common Pitfalls or Variants

Common pitfalls

Forgetting that students may apply operators in non-standard order, giving alternative valid results.
Recomputing subexpression values without memoization, causing exponential time.
Assuming all answers outside the correct one get zero points, ignoring partial scoring rules.

Follow-up variants

Expressions may include subtraction or division operators with similar scoring rules.
Multiple-digit numbers instead of single-digit, requiring careful parsing.
Changing point system to reward only top-k alternative answers instead of all.

FAQ

What is the main pattern used in this problem?

The problem is best solved using state transition dynamic programming to enumerate all possible subexpression results efficiently.

How do I handle partial scoring for alternative evaluations?

Compute all possible outcomes of the expression using different operator orders and compare each student answer to this set for partial points.

Can I extend this approach to expressions with multi-digit numbers?

Yes, but you need to parse numbers correctly and ensure your DP memoization covers the expanded range of subexpressions.

What causes exponential time complexity here?

Without memoization, every subexpression is recomputed for each operator split, leading to exponential evaluations in the number of operators.

How does GhostInterview help with The Score of Students Solving Math Expression?

It provides step-by-step computation of all possible results, flags alternative evaluation paths, and calculates total student points efficiently using DP.

terminal

Solution

Solution 1: Dynamic Programming (Interval DP)

First, we design a function $cal(s)$ to calculate the result of a valid mathematical expression that only contains single-digit numbers. The correct answer is $x = cal(s)$.

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

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

Continue Practicing

#1728 cat and mouse ii #1569 number of ways to reorder array to get same bst #1994 the number of good subsets