Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2019.html
2019. The Score of Students Solving Math Expression (Hard)
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 used the incorrect order of operations, once or multiple times, 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 used this incorrect order of operations: 7+3=10, 10*1=10, 10*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 used this incorrect order of operations: 3+5=8, 8*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 used some incorrect order of operations, 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
Similar Questions:
Solution 1. DP
Let dp[i][j] be the possible values the students can get using s[i..j].
dp[i][i] = { s[i] - '0' }
For dp[i][j], we enumerate all the indexes k of the operators between i and j. Let a and b be elements in dp[i][k-1] and dp[k+1][j].
- If
s[k] == '+', we inserta + bintodp[i][j] - If
s[k] == '*', we inserta * bintodp[i][j]
Bottom-up DP:
// OJ: https://leetcode.com/problems/the-score-of-students-solving-math-expression/
// Time: O(N^3 * 1000^2)
// Space: O(N^2 * 1000)
class Solution {
public:
int eval(string &s, int first, int last) {
if (first == last) return s[first] - '0';
int i = first + 1;
for (; i <= last && s[i] == '*'; i += 2); // find the first '+'
if (i <= last) return eval(s, first, i - 1) + eval(s, i + 1, last); // calculate the first '+'
int ans = 1;
for (int i = first; i <= last; i += 2) ans *= s[i] - '0';
return ans; // If there is no `+`, calculate all the `*`s
}
int scoreOfStudents(string s, vector<int>& A) {
int ans = 0, N = s.size(), correct = eval(s, 0, N - 1);
unordered_set<long long> dp[32][32];
for (int i = 0; i < N; i += 2) dp[i][i].insert(s[i] - '0');
for (int i = N - 3; i >= 0; i -= 2) {
for (int j = i + 2; j < N; j += 2){
for (int k = i + 1; k < j; k += 2) { // For s[i..j], enumerate every operators' indexes `k`
for (auto a : dp[i][k - 1]) {
for (auto b : dp[k + 1][j]) {
int val = s[k] == '+' ? a + b : a * b;
if (val <= 1000) dp[i][j].insert(val);
}
}
}
}
}
for (int n : A) {
if (n == correct) ans += 5;
else if (dp[0][N - 1].count(n)) ans += 2;
}
return ans;
}
};
Or Top-down DP:
// OJ: https://leetcode.com/problems/the-score-of-students-solving-math-expression/
// Time: O(N^3 * 1000^2)
// Space: O(N^2 * 1000)
class Solution {
int eval(string &s, int first, int last) {
if (first == last) return s[first] - '0';
auto it = find(begin(s) + first, begin(s) + last + 1, '+');
if (it == begin(s) + last + 1) {
int ans = 1;
for (int j = first; j <= last; j += 2) ans *= s[j] - '0';
return ans;
}
return eval(s, first, it - begin(s) - 1) + eval(s, it - begin(s) + 1, last);
}
unordered_set<int> m[32][32] = {};
unordered_set<int> *dp(string &s, int first, int last) {
if (m[first][last].size()) return &m[first][last];
for (int i = first + 1; i < last; i += 2) {
for (int a : *dp(s, first, i - 1)) {
for (int b : *dp(s, i + 1, last)) {
int val = s[i] == '+' ? a + b : a * b;
if (val <= 1000) m[first][last].insert(val);
}
}
}
return &m[first][last];
}
public:
int scoreOfStudents(string s, vector<int>& A) {
int correct = eval(s, 0, s.size() - 1), ans = 0;
for (int i = 0; i < s.size(); i += 2) m[i][i].insert(s[i] - '0');
auto all = dp(s, 0, s.size() - 1);
for (int n : A) {
if (n == correct) ans += 5;
else if (all->count(n)) ans += 2;
}
return ans;
}
};