题解 | #最小代价使括号有效#

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return string字符串
     */
    string minRemoveToMakeValid(string s) {
        // write code here
        this->s = s;
        dfs(0);
        string ret = "";
        for (auto ch : ans) ret += ch;
        return ret;
    }

    void dfs(int i) {
        // 到达结尾
        if (i >= s.size()) {
            if (stk.size() > 0) return; // 栈不空，是非法串
            if (path.size() > ans.size()) {
                ans.clear();
                for (auto ch : path) ans.push_back(ch);
            }
            return;
        }
        // 不是括号
        if (!isBrace(s[i])) {
            path.push_back(s[i]);
            dfs(i + 1);
            path.pop_back();
            return;
        }

        // 研究左括号
        if (isLeftBrace(s[i])) {
            // 不删除 s[i]，入栈 & 回溯
            stk.push_back(s[i]);
            path.push_back(s[i]);
            dfs(i + 1);
            path.pop_back();
            stk.pop_back();
            // 删除 s[i]
            dfs(i + 1);
            return;
        }

        // 研究右括号
        if (stk.empty()) { // 没有左括号与之匹配
            // 删除 s[i] 
            dfs(i + 1); 
        } else if (isMatch(stk.back(), s[i])) { // 匹配
            // 出栈 & 回溯
            char tmp = stk.back();
            stk.pop_back();
            path.push_back(s[i]);
            dfs(i + 1);
            path.pop_back();
            stk.push_back(tmp);
        } else { // 不匹配
            // 删除 s[i] 
            dfs(i + 1); 
        }
    }

    bool isLeftBrace(char ch) {
        return ch == '(' ||
               ch == '[' ||
               ch == '{' ;
    }

    bool isRightBrace(char ch) {
        return  ch == ')' ||
                ch == ']' ||
                ch == '}' ;
    }

    bool isBrace(char ch) {
        return isLeftBrace(ch) || isRightBrace(ch);
    }

    bool isMatch(char l, char r) {
        return l == '(' && r == ')' ||
               l == '[' && r == ']' ||
               l == '{' && r == '}' ;
    }

    vector<char> stk = vector<char>();
    string s;
    vector<char> ans = vector<char>();
    vector<char> path = vector<char>();

};

回溯