301. Remove Invalid Parentheses

1249. Minimum Remove to Make Valid Parentheses的followup
time worst case O(n²) “)a)a)a)a)a” 因为需要最后的结果

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        remove(s, 0, 0, '(', ')');
        return res;
    }

    void remove(const string &s, int sb, int rb, char lp, char rp) {
        if (int i = search(s, sb, lp, rp); i == s.length()) {
            string t(rbegin(s), rend(s));
            if (lp == '(') {
                remove(t, 0, 0, rp, lp);
            } else {
                res.push_back(t);
            }
        } else {
            for (int j = rb; j <= i; ++j) {
                if (s[j] == rp && (j == rb || s[j] != s[j - 1])) {
                    remove(s.substr(0, j) + s.substr(j + 1), i, j, lp, rp);
                }
            }
        }
    }

    int search(const string &s, int b, char lp, char rp) { // 找到第一个不匹配的右括号
        int i = b;
        for (int cnt = 0; i < s.length(); ++i) {
            cnt += (s[i] == rp) ? -1 : (s[i] == lp);
            if (cnt < 0) break;
        }
        return i;
    }

    vector<string> res;
};

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        remove(s, 0, 0, '(', ')');
        return res;
    }

    void remove(const string &s, int sb, int rb, char lp, char rp) {
        int i = sb, cnt = 0;
        while (i < s.length() && cnt >= 0) { // 遍历字符串直到找到第一个匹配不上的『右括号』
            cnt += (s[i] == rp ? -1 : s[i] == lp); // 注意字符串里可能还有非左右括号的字符
            ++i;
        }
        if (cnt >= 0) { // 如果没有匹配不上的『右括号』则翻转字符串尝试删除匹配不上的『左括号』
            string t(rbegin(s), rend(s));
            if (lp == '(') {
                remove(t, 0, 0, rp, lp);
            } else { // 如果两种case都已经尝试过了，则当前字符串已经全部匹配
                res.push_back(t);
            }
        } else { // 当找到第一个匹配不上的『右括号』
            --i; // 先回退到这个匹配不上的『右括号』
            for (int j = rb; j <= i; ++j) { // 从上次删除过的位置开始一直到当前这个匹配不上的为止，尝试删除『右括号』并拼成新字符串
                if (s[j] == rp && (j == rb || s[j - 1] != s[j])) { // 跳过连续『右括号』去重
                    remove(s.substr(0, j) + s.substr(j + 1), i, j, lp, rp); // 下个iteration的删除要从这次删除的位置j开始
                }
            }
        }
    }

    vector<string> res;
};

O(2ⁿ) time

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        int l = 0, r = 0;
        for (char c : s) { // 先统计需要删除几个左括号和右括号（无法匹配）
            if (c == '(') {
                ++l;
            } else if (c == ')') {
                l > 0 ? --l : ++r;
            }
        }
        helper(s, 0, l, r);
        return res;
    }

private:
    void helper(string s, int b, int l, int r) {
        if (l == 0 && r == 0) { // 如果多余的左括号和右括号都已经删除
            if (isValid(s)) // 判断当前的字符串是否合法（因为是盲删的所以可能得到的字符串不合法）
                res.push_back(s);
            return;
        }
        for (int i = b; i < s.length(); ++i) {
            if (i > b && s[i - 1] == s[i]) continue; // 去重，比如连续两个右括号，删一个即可
            if (s[i] == '(' && l > 0) { // 盲删左括号
                helper(s.substr(0, i) + s.substr(i + 1), i, l - 1, r); // 从i开始也是一种去重
            } else if (s[i] == ')' && r > 0) { // 盲删右括号
                helper(s.substr(0, i) + s.substr(i + 1), i, l, r - 1); // 切记不要用s.erase因为是循环删除，所以前面删除以后会影响后边
            }
        }
    }

    bool isValid(string s) {
        int cnt = 0;
        for (char c : s) {
            if (c == '(') {
                ++cnt;
            } else if (c == ')') {
                if (--cnt < 0) return false;
            }
        }
        return cnt == 0;
    }

    vector<string> res;
};