algo-aha

验证字符串是 abc 的多次嵌套

• https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/

bool isValid(string S) {
    // 用栈，从左到右扫，遇到c时弹出末尾的b和a
    string stk;
    for (char c : S) {
        if (c == 'c') {
            if (stk.empty() || stk.back() != 'b') return false;
            stk.pop_back();
            if (stk.empty() || stk.back() != 'a') return false;
            stk.pop_back();
        } else {
            stk.push_back(c);
        }
    }
    return stk.empty();
}

不断删除连续 k 个相同字母

• https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/

string removeDuplicates(string s, int k) {
    vector<pair<char, int>> stk;
    for (char c : s) {
        if (stk.empty() || stk.back().first != c) {
            stk.push_back({c, 1});
        } else if (++stk.back().second == k) {
            stk.pop_back();
        }
    }
    string ans;
    for (auto &e : stk) {
        ans += string(e.second, e.first);
    }
    return ans;
}

反转括号中的串，括号不输出

• https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/

string reverseParentheses(string s) {
    string ans;
    stack<int> open;
    for (char c : s) {
        if (c == '(') {
            open.push(ans.size());
        } else if (c == ')') {
            int pos = open.top();  open.pop();
            reverse(ans.begin() + pos, ans.end());
        } else {
            ans += c;
        }
    }
    return ans;
}