1717. Maximum Score From Removing Substrings
原本我也想说这个该不会是DP吧
弄了老半天结果这个做Greedy会是最佳解
那就跟检查括号有没有对应的题目差不多
就一个stack然后东西放进去，match到的话就pop
class Solution {
public:
int removeSubstr(string &s, const string &p, int score) {
int totalScore = 0;
string temp;
for (char c: s) {
if (!temp.empty() && temp.back() == p[0] && c == p[1]) {
temp.pop_back();
totalScore += score;
}
else
temp.push_back(c);
}
s = temp;
return totalScore;
}
int maximumGain(string s, int x, int y) {
int score = 0;
string firstPass = (x > y)? "ab": "ba";
string secondPass = (x > y)? "ba": "ab";
score += removeSubstr(s, firstPass, max(x, y));
score += removeSubstr(s, secondPass, min(x, y));
return score;
}
};
写完之后想到一件事
removeSubstr有side effect其实这样写蛮丑的