2019. The Score of Students Solving Math Expression LeetCode Solution
In this guide, you will get 2019. The Score of Students Solving Math Expression LeetCode Solution with the best time and space complexity. The solution to The Score of Students Solving Math Expression problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of The Score of Students Solving Math Expression
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 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:
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.
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
Complexity Analysis
Time Complexity: O(|\texttt{s}|^5 + n)
Space Complexity: O(|\texttt{s}|^3 + n)
2019. The Score of Students Solving Math Expression LeetCode Solution in C++
class Solution {
public:
int scoreOfStudents(string s, vector<int>& answers) {
const int n = s.length() / 2 + 1;
const unordered_map<char, function<int(int, int)>> func{
{'+', plus<int>()}, {'*', multiplies<int>()}};
int ans = 0;
vector<vector<unordered_set<int>>> dp(n, vector<unordered_set<int>>(n));
unordered_map<int, int> count;
for (int i = 0; i < n; ++i)
dp[i][i].insert(s[i * 2] - '0');
for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
const int j = i + d;
for (int k = i; k < j; ++k) {
const char op = s[k * 2 + 1];
for (const int a : dp[i][k])
for (const int b : dp[k + 1][j]) {
const int res = func.at(op)(a, b);
if (res <= 1000)
dp[i][j].insert(res);
}
}
}
const int correctAnswer = eval(s);
for (const int answer : answers)
++count[answer];
for (const auto& [answer, freq] : count)
if (answer == correctAnswer)
ans += 5 * freq;
else if (dp[0][n - 1].contains(answer))
ans += 2 * freq;
return ans;
}
private:
int eval(const string& s) {
int ans = 0;
int prevNum = 0;
int currNum = 0;
char op = '+';
for (int i = 0; i < s.length(); ++i) {
const char c = s[i];
if (isdigit(c))
currNum = currNum * 10 + (c - '0');
if (!isdigit(c) || i == s.length() - 1) {
if (op == '+') {
ans += prevNum;
prevNum = currNum;
} else if (op == '*') {
prevNum = prevNum * currNum;
}
op = c;
currNum = 0;
}
}
return ans + prevNum;
}
}; /* code provided by PROGIEZ */
2019. The Score of Students Solving Math Expression LeetCode Solution in Java
class Solution {
public int scoreOfStudents(String s, int[] answers) {
final int n = s.length() / 2 + 1;
int ans = 0;
Set<Integer>[][] dp = new Set[n][n];
Map<Integer, Integer> count = new HashMap<>();
for (int i = 0; i < n; ++i)
for (int j = i; j < n; ++j)
dp[i][j] = new HashSet<>();
for (int i = 0; i < n; ++i)
dp[i][i].add(s.charAt(i * 2) - '0');
for (int d = 1; d < n; ++d)
for (int i = 0; i + d < n; ++i) {
final int j = i + d;
for (int k = i; k < j; ++k) {
final char op = s.charAt(k * 2 + 1);
for (final int a : dp[i][k])
for (final int b : dp[k + 1][j]) {
final int res = func(op, a, b);
if (res <= 1000)
dp[i][j].add(res);
}
}
}
final int correctAnswer = eval(s);
for (final int answer : answers)
count.merge(answer, 1, Integer::sum);
for (final int answer : count.keySet())
if (answer == correctAnswer)
ans += 5 * count.get(answer);
else if (dp[0][n - 1].contains(answer))
ans += 2 * count.get(answer);
return ans;
}
private int eval(final String s) {
int ans = 0;
int currNum = 0;
int prevNum = 0;
char op = '+';
for (int i = 0; i < s.length(); ++i) {
final char c = s.charAt(i);
if (Character.isDigit(c))
currNum = currNum * 10 + (c - '0');
if (!Character.isDigit(c) || i == s.length() - 1) {
if (op == '+') {
ans += prevNum;
prevNum = currNum;
} else if (op == '*') {
prevNum = prevNum * currNum;
}
op = c;
currNum = 0;
}
}
return ans + prevNum;
}
private int func(char op, int a, int b) {
if (op == '+')
return a + b;
return a * b;
}
} // code provided by PROGIEZ
2019. The Score of Students Solving Math Expression LeetCode Solution in Python
class Solution:
def scoreOfStudents(self, s: str, answers: list[int]) -> int:
n = len(s) // 2 + 1
ans = 0
func = {'+': operator.add, '*': operator.mul}
dp = [[set() for j in range(n)] for _ in range(n)]
for i in range(n):
dp[i][i].add(int(s[i * 2]))
for d in range(1, n):
for i in range(n - d):
j = i + d
for k in range(i, j):
op = s[k * 2 + 1]
for a in dp[i][k]:
for b in dp[k + 1][j]:
res = func[op](a, b)
if res <= 1000:
dp[i][j].add(res)
correctAnswer = eval(s)
for answer, freq in collections.Counter(answers).items():
if answer == correctAnswer:
ans += 5 * freq
elif answer in dp[0][n - 1]:
ans += 2 * freq
return ans # code by PROGIEZ
