LeetCode 2019 - The Score of Students Solving Math Expression

The problem gives us a mathematical expression string s containing only: - Single digit numbers 0-9 - Addition operators + - Multiplication operators The expression is guaranteed to be valid.

leetcodehardarrayhash-tablemathstringdynamic-programmingstackmemoization

LeetCode Problem 2019

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Math, String, Dynamic Programming, Stack, Memoization

Solution

LeetCode 2019, The Score of Students Solving Math Expression

Problem Understanding

The problem gives us a mathematical expression string s containing only:

  • Single digit numbers 0-9
  • Addition operators +
  • Multiplication operators *

The expression is guaranteed to be valid. For example:

3+5*2
7+3*1*2

Students were supposed to evaluate the expression using the correct precedence rules:

  1. Perform all multiplications from left to right
  2. Then perform all additions from left to right

This is standard arithmetic precedence where multiplication happens before addition.

We are also given an array answers, where each value represents a student's submitted answer. We must assign points according to the following grading rules:

  • If the answer equals the correct result, award 5 points
  • Otherwise, if the answer could result from a different but valid parenthesization where arithmetic itself is still correct, award 2 points
  • Otherwise, award 0 points

The important subtlety is understanding what counts as a "wrong order" answer.

Students may incorrectly evaluate the expression by choosing arbitrary parenthesizations, effectively changing operator precedence. However:

  • They must still perform arithmetic correctly
  • Only results obtainable from valid binary expression groupings count
  • Intermediate and final values must stay within the allowed range
  • We only care about results up to 1000

For example:

3+5*2

Correct evaluation:

3 + (5*2) = 13

Possible incorrect evaluation:

(3+5) * 2 = 16

So 16 earns 2 points.

The constraints are very important:

  • Expression length is at most 31
  • There are at most 15 operators
  • Therefore, there are at most 16 numbers

This is small enough for interval dynamic programming.

The main challenge is efficiently computing all possible results obtainable through incorrect parenthesizations.

Important edge cases include:

  • Expressions where incorrect evaluation accidentally equals the correct answer
  • Expressions containing 0
  • Duplicate answers
  • Many different parenthesizations producing the same value
  • Intermediate results exceeding 1000, which should be discarded

Approaches

Brute Force Approach

A brute force solution would generate every possible parenthesization of the expression and evaluate each one.

This is equivalent to generating all binary expression trees. The number of parenthesizations grows according to Catalan numbers:

C(n) ≈ 4^n / (n^(3/2))

For 15 operators, this becomes extremely large.

The brute force algorithm would:

  1. Recursively split the expression at every operator
  2. Compute all possible results for the left and right subexpressions
  3. Combine them according to the operator
  4. Collect all generated values
  5. Compare student answers against the resulting set

Although this produces correct results, recomputing the same subexpressions repeatedly makes it far too slow.

Key Insight

The crucial observation is that many recursive calls solve the same subproblem repeatedly.

For example:

3+5*2+4

The subexpression 5*2 may appear in many recursive decompositions.

Instead of recomputing results every time, we can use interval dynamic programming with memoization.

For every substring representing a valid subexpression, we compute:

all possible values obtainable from that subexpression

Then:

  • Store the results in a memo table
  • Reuse them whenever needed
  • Combine left and right results efficiently

Since there are only at most 16 numbers, the total number of subexpressions is manageable.

We also aggressively prune values greater than 1000, because student answers never exceed 1000.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Recomputes identical subexpressions repeatedly
Optimal O(n³ × m²) O(n² × m) Interval DP with memoized result sets

Here:

  • n is the number of numbers in the expression
  • m is the maximum number of distinct results per interval

Algorithm Walkthrough

Step 1: Parse the Expression

Separate the expression into:

  • A list of numbers
  • A list of operators

For example:

"3+5*2"

becomes:

nums = [3, 5, 2]
ops = ['+', '*']

This makes interval processing much easier.

Step 2: Compute the Correct Answer

We must evaluate the expression using standard precedence rules.

Because multiplication has higher precedence than addition, we can process the expression as follows:

  1. Maintain a running multiplication product
  2. Whenever we encounter +, add the accumulated product to the total
  3. Reset the product with the next number

For:

3+5*2

we compute:

3 + (5*2) = 13

This gives the official correct answer worth 5 points.

Step 3: Define the DP State

We define:

dp(l, r)

as:

all possible results obtainable from nums[l:r+1]

Each state returns a set of integers.

For example:

dp(0, 2)

for:

3+5*2

may produce:

{13, 16}

Step 4: Base Case

If the interval contains only one number:

l == r

then the only possible value is that number itself.

Example:

dp(1,1) = {5}

Step 5: Split at Every Operator

For every operator position k between l and r:

  1. Recursively compute all left results
  2. Recursively compute all right results
  3. Combine every left value with every right value

If the operator is +:

value = left + right

If the operator is *:

value = left * right

Step 6: Prune Large Values

The problem guarantees answers are between 0 and 1000.

Any intermediate result larger than 1000 can be ignored.

This dramatically reduces the number of stored states.

Step 7: Memoize Results

Many intervals repeat during recursion.

Memoization ensures each interval is computed only once.

Without memoization, runtime would explode exponentially.

Step 8: Grade Student Answers

Now we have:

  • correct_answer
  • possible_answers

For each student answer:

  • If it equals correct_answer, add 5
  • Else if it exists in possible_answers, add 2
  • Otherwise add 0

Why it works

The recursion considers every possible binary partition of the expression. Every valid parenthesization corresponds to exactly one recursive decomposition tree, so every obtainable value is generated.

Memoization guarantees that each subexpression is solved once, while set storage prevents duplicate values from growing uncontrollably.

Because we combine all left and right possibilities for every split point, the DP enumerates exactly all valid incorrect evaluations.

Python Solution

from typing import List
from functools import lru_cache

class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        nums = []
        ops = []

        for i, ch in enumerate(s):
            if i % 2 == 0:
                nums.append(int(ch))
            else:
                ops.append(ch)

        # Compute correct answer using standard precedence
        correct = 0
        current = nums[0]

        for i, op in enumerate(ops):
            if op == '*':
                current *= nums[i + 1]
            else:
                correct += current
                current = nums[i + 1]

        correct += current

        @lru_cache(None)
        def dp(left: int, right: int):
            if left == right:
                return {nums[left]}

            results = set()

            for k in range(left, right):
                left_values = dp(left, k)
                right_values = dp(k + 1, right)

                for a in left_values:
                    for b in right_values:
                        if ops[k] == '+':
                            value = a + b
                        else:
                            value = a * b

                        if value <= 1000:
                            results.add(value)

            return results

        possible = dp(0, len(nums) - 1)

        score = 0

        for ans in answers:
            if ans == correct:
                score += 5
            elif ans in possible:
                score += 2

        return score

The implementation begins by parsing the expression into separate number and operator arrays. This simplifies interval handling because each subproblem can be represented by number indices instead of substring parsing.

The correct answer is computed using multiplication precedence. Instead of building a full parser, we maintain a running multiplication group and add completed groups whenever a + appears.

The recursive dp(left, right) function returns all possible values obtainable from the subexpression spanning indices left through right.

The memoization decorator is critical because many intervals repeat. Without caching, the recursion would recompute the same subexpressions many times.

For every operator position k, the function combines every left result with every right result according to the operator. This systematically explores every valid parenthesization.

The value <= 1000 pruning keeps the state space manageable and matches the problem constraints.

Finally, the grading loop checks whether each answer is exactly correct or merely obtainable through incorrect precedence.

Go Solution

package main

func scoreOfStudents(s string, answers []int) int {
	nums := []int{}
	ops := []byte{}

	for i := 0; i < len(s); i++ {
		if i%2 == 0 {
			nums = append(nums, int(s[i]-'0'))
		} else {
			ops = append(ops, s[i])
		}
	}

	// Compute correct answer
	correct := 0
	current := nums[0]

	for i, op := range ops {
		if op == '*' {
			current *= nums[i+1]
		} else {
			correct += current
			current = nums[i+1]
		}
	}

	correct += current

	type Key struct {
		l int
		r int
	}

	memo := map[Key]map[int]bool{}

	var dp func(int, int) map[int]bool

	dp = func(left int, right int) map[int]bool {
		key := Key{left, right}

		if val, exists := memo[key]; exists {
			return val
		}

		results := map[int]bool{}

		if left == right {
			results[nums[left]] = true
			memo[key] = results
			return results
		}

		for k := left; k < right; k++ {
			leftValues := dp(left, k)
			rightValues := dp(k+1, right)

			for a := range leftValues {
				for b := range rightValues {
					value := 0

					if ops[k] == '+' {
						value = a + b
					} else {
						value = a * b
					}

					if value <= 1000 {
						results[value] = true
					}
				}
			}
		}

		memo[key] = results
		return results
	}

	possible := dp(0, len(nums)-1)

	score := 0

	for _, ans := range answers {
		if ans == correct {
			score += 5
		} else if possible[ans] {
			score += 2
		}
	}

	return score
}

The Go implementation follows the same algorithmic structure as the Python version.

The primary difference is memoization handling. Since Go does not provide a built in memoization decorator like Python's lru_cache, we explicitly store computed intervals inside a map keyed by (left, right).

Sets are represented using:

map[int]bool

because Go does not have a native set type.

All arithmetic safely fits within Go's standard integer range under the given constraints.

Worked Examples

Example 1

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

Step 1: Parse Expression

Component Value
nums [7, 3, 1, 2]
ops ['+', '', '']

Step 2: Correct Evaluation

Compute multiplication first:

3*1*2 = 6
7+6 = 13

Correct answer:

13

Step 3: DP Computation

Base intervals

Interval Results
dp(0,0) {7}
dp(1,1) {3}
dp(2,2) {1}
dp(3,3) {2}

Length 2 intervals

Interval Computation Results
dp(0,1) 7+3 {10}
dp(1,2) 3*1 {3}
dp(2,3) 1*2 {2}

Length 3 intervals

For dp(0,2):

Split at +:

7 + (3*1) = 10

Split at *:

(7+3) * 1 = 10

Results:

{10}

For dp(1,3):

3 * (1*2) = 6
(3*1) * 2 = 6

Results:

{6}

Full interval

For dp(0,3):

Split at first operator:

7 + 6 = 13

Split at second operator:

10 * 2 = 20

Split at third operator:

10 * 2 = 20

Final possible values:

{13, 20}

Step 4: Grade Answers

Answer Result Points
20 Incorrect but possible 2
13 Correct 5
42 Impossible 0

Total:

7

Example 2

s = "3+5*2"
answers = [13,0,10,13,13,16,16]

Correct Answer

3 + (5*2) = 13

Possible DP Results

Parenthesization Value
3 + (5*2) 13
(3+5) * 2 16

Possible set:

{13, 16}

Grading

Answer Points
13 5
0 0
10 0
13 5
13 5
16 2
16 2

Total:

19

Example 3

s = "6+0*1"
answers = [12,9,6,4,8,6]

Correct Answer

6 + (0*1) = 6

Alternative Parenthesization

(6+0) * 1 = 6

Even incorrect precedence still gives 6.

According to the rules, exact correctness always gets 5 points.

Grading

Answer Points
12 0
9 0
6 5
4 0
8 0
6 5

Total:

10

Complexity Analysis

Measure Complexity Explanation
Time O(n³ × m²) For each interval and split, combine left and right result sets
Space O(n² × m) Memoized result sets for all intervals

Here:

  • n is the number of numbers in the expression
  • m is the maximum number of distinct values stored per interval

The number of intervals is:

O(n²)

For each interval, we try all split positions:

O(n)

For every split, we combine two result sets, which contributes:

O(m²)

In practice, pruning values greater than 1000 keeps m relatively small, making the solution efficient enough for the constraints.

Test Cases

from typing import List

class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        from functools import lru_cache

        nums = []
        ops = []

        for i, ch in enumerate(s):
            if i % 2 == 0:
                nums.append(int(ch))
            else:
                ops.append(ch)

        correct = 0
        current = nums[0]

        for i, op in enumerate(ops):
            if op == '*':
                current *= nums[i + 1]
            else:
                correct += current
                current = nums[i + 1]

        correct += current

        @lru_cache(None)
        def dp(l, r):
            if l == r:
                return {nums[l]}

            results = set()

            for k in range(l, r):
                for a in dp(l, k):
                    for b in dp(k + 1, r):
                        if ops[k] == '+':
                            val = a + b
                        else:
                            val = a * b

                        if val <= 1000:
                            results.add(val)

            return results

        possible = dp(0, len(nums) - 1)

        score = 0

        for ans in answers:
            if ans == correct:
                score += 5
            elif ans in possible:
                score += 2

        return score

sol = Solution()

assert sol.scoreOfStudents("7+3*1*2", [20,13,42]) == 7  # provided example 1

assert sol.scoreOfStudents(
    "3+5*2",
    [13,0,10,13,13,16,16]
) == 19  # provided example 2

assert sol.scoreOfStudents(
    "6+0*1",
    [12,9,6,4,8,6]
) == 10  # provided example 3

assert sol.scoreOfStudents("1+2", [3,2,1]) == 5  # smallest valid expression

assert sol.scoreOfStudents("2*3", [6,5,4]) == 5  # multiplication only

assert sol.scoreOfStudents("1+2+3", [6,7]) == 5  # only one possible result

assert sol.scoreOfStudents("2*3+4", [10,14]) == 7  # different parenthesizations

assert sol.scoreOfStudents("0*0+0", [0]) == 5  # many parenthesizations same answer

assert sol.scoreOfStudents("9*9*9", [729,1000]) == 5  # large multiplication

assert sol.scoreOfStudents(
    "1+2*3+4",
    [11,13,21]
) == 7  # mix of correct and incorrect answers

assert sol.scoreOfStudents(
    "1+1+1+1+1",
    [5,4,3]
) == 5  # repeated additions only

assert sol.scoreOfStudents(
    "2*2*2*2",
    [16,8]
) == 5  # repeated multiplications only

Test Summary

Test Why
"7+3*1*2" Validates mixed operators and alternative parenthesizations
"3+5*2" Validates incorrect precedence answers
"6+0*1" Validates overlapping correct and incorrect results
"1+2" Smallest valid expression
"2*3" Pure multiplication
"1+2+3" Pure addition
"2*3+4" Mixed precedence behavior
"0*0+0" Zero handling
"9*9*9" Large multiplication result
"1+2*3+4" Multiple valid alternative values
"1+1+1+1+1" Many additions
"2*2*2*2" Many multiplications

Edge Cases

Edge Case 1: Incorrect Evaluation Equals Correct Evaluation

Consider:

6+0*1

Correct precedence gives:

6 + (0*1) = 6

Incorrect precedence may give:

(6+0) * 1 = 6

Both produce the same value.

A buggy implementation might incorrectly award only 2 points because the value appears in the alternative result set.

Our implementation avoids this by always checking:

if ans == correct:

before checking whether it belongs to the alternative set.

Edge Case 2: Duplicate Student Answers

Students may submit the same answer multiple times.

For example:

answers = [13,13,13]

Each student must be graded independently.

A buggy implementation using frequencies incorrectly could undercount or overcount points.

Our solution iterates through every answer individually and adds points independently.

Edge Case 3: Exploding Number of Intermediate Results

Expressions with many operators can generate many possible parenthesizations.

Without pruning, result sets could grow extremely large.

For example:

9*9*9+9*9

can generate many combinations.

The constraint that student answers are at most 1000 allows us to safely discard larger values immediately:

if value <= 1000:

This dramatically limits memory usage and runtime while preserving correctness.