The score of students solving math expression

Array Hash Table Math String Dynamic Programming Stack Memoization

34.0% acceptance

Feb 25, 2026

281

You are given a string s containing digits 0-9, '+', and '*' representing a math expression. Students may solve it with wrong order (treating all operators as left-to-right, ignoring precedence). Grade: 5 points if answer is correct, 2 points if it's a possible wrong answer, 0 otherwise. Return sum of all student points.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn score_of_students(s: String, answers: Vec<i32>) -> i32 {
    let s = s.as_bytes();
    // Parse numbers and operators
    let mut nums: Vec<i32> = vec![];
    let mut ops: Vec<u8> = vec![];
    for i in (0..s.len()).step_by(2) {
      nums.push((s[i] - b'0') as i32);
      if i + 1 < s.len() { ops.push(s[i+1]); }
    }
    let n = nums.len();
    
    // Compute correct answer using standard precedence
    let correct = {
      let mut stack: Vec<i32> = vec![nums[0]];
      for i in 0..ops.len() {
        if ops[i] == b'*' {
          let top = stack.pop().unwrap();
          stack.push(top * nums[i+1]);
        } else {
          stack.push(nums[i+1]);
        }
      }
      stack.iter().sum::<i32>()
    };
    
    // DP to find all possible wrong answers
    // dp[i][j] = set of possible values for subexpression from index i to j (inclusive)
    // Cap at 1001 to limit computation
    const MAX: i32 = 1001;
    let mut dp: Vec<Vec<std::collections::HashSet<i32>>> = 
      vec![vec![std::collections::HashSet::new(); n]; n];
    for i in 0..n { dp[i][i].insert(nums[i]); }
    
    for len in 2..=n {
      for i in 0..=(n - len) {
        let j = i + len - 1;
        for k in i..j {
          let op = ops[k];
          let left = dp[i][k].clone();
          let right = dp[k+1][j].clone();
          for &l in &left {
            for &r in &right {
              let v = if op == b'+' { l + r } else { l * r };
              if v <= MAX { dp[i][j].insert(v); }
            }
          }
        }
      }
    }
    
    let possible = &dp[0][n-1];
    let mut total = 0;
    for &a in &answers {
      if a == correct {
        total += 5;
      } else if possible.contains(&a) {
        total += 2;
      }
    }
    total
  }
}