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其實這樣寫蠻醜的