最长有效括号对

int longestValidParentheses(string s) {
    int ans = 0;
    stack<int> stk; // 没匹配掉的压入栈中，保存下标
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == ')' && !stk.empty() && s[stk.top()] == '(') {
            stk.pop();
            int lastMismatch = stk.empty() ? -1 : stk.top();
            ans = max(ans, i - lastMismatch); // 前开后闭
        } else {
            stk.push(i);
        }
    }
    return ans;
}

所有有效括号对

vector<string> generateParenthesis(int n) {
    vector<string> ans;
    search(n, n, "", ans);
    return ans;
}

void search(int remainL, int remainR, string paren, vector<string> &ans) {
    // 确保 0 <= remainL <= remainR
    if (remainL == 0 && remainR == 0) {
        ans.push_back(paren);
        return;
    }
    
    if (remainL > 0) search(remainL - 1, remainR, paren + '(', ans);
    if (remainL < remainR) search(remainL, remainR - 1, paren + ')', ans);
}

仅含 ( ) * 的串是否有效

  • https://leetcode.com/problems/valid-parenthesis-string
bool checkValidString(string s) {
    // 设多出的左括号数leftDiff的范围为[lo, hi]。
    // 1. 遇到'('，左括号多1，lo++, hi++；
    // 2. 遇到')'，左括号少1，lo--, hi--；
    // 3. 遇到'*'，它可以是'('、空串、')'，[lo, hi]内的每个值都可-1、+0、+1，整体扩张lo--, hi++。
    // 综上，遇到'('时lo++、其他lo--；遇到')'时hi--，其他hi++。 
    int lo = 0, hi = 0;
    for (char c : s) {
        lo += (c == '(') ? 1 : -1;
        hi += (c == ')') ? -1 : 1;
        // 在扫描过程中，一旦hi<0，leftDiff<0，串无效
        if (hi < 0) return false;
        // 而lo<0的部分可以直接丢弃，因为有效串的leftDiff>=0
        lo = max(lo, 0);
    }
    // 最终能够leftDiff==0，串才有效
    return lo == 0;
}

删除最少的无用括号使剩下的括号串有效，返回所有可能

vector<string> removeInvalidParentheses(string s) {
    // 有多少左右括号不匹配待删除，
    // rmL和rmR将作为dfs的剪枝条件
    int rmL = 0, rmR = 0;
    for (char c : s) {
        if (c == '(') {
            rmL++;
        } else if (c == ')') {
            if (rmL > 0) rmL--; // 匹配
            else rmR++;
        }
    }

    vector<string> ans;
    remove(s, 0, 0, rmL, rmR, ans);
    return ans;
}

// s[..idx)的左括号比右括号多moreL，s[idx..]有rmL个'('待删除、rmR个')'待删除
void remove(const string &s, int idx, int moreL, int rmL, int rmR, vector<string> &ans) {
    if (moreL < 0 || rmL < 0 || rmR < 0) return;
    const int N = s.size();

    for (int i = idx; i < N && moreL >= 0; i++) {
        if (s[i] == '(') {
            if (rmL > 0 && (i == idx || s[i] != s[i-1])) { // 连续'('只删第一个
                remove(s.substr(0, i) + s.substr(i + 1), i, moreL, rmL - 1, rmR, ans);
            }
            moreL++;
        } else if (s[i] == ')') {
            if (rmR > 0 && (i == idx || s[i] != s[i-1])) {
                remove(s.substr(0, i) + s.substr(i + 1), i, moreL, rmL, rmR - 1, ans);
            }
            moreL--;
        }
    }

    if (moreL == 0 && rmL == 0 && rmR == 0) {
        ans.push_back(s);
    }
}

括号按深度得分

int scoreOfParentheses(string S) {
    // 深度depth的"()"贡献2^depth分
    int depth = 0, ans = 0;
    for (int i = 0; i < S.size(); i++) {
        if (S[i] == '(') depth++;
        else {
            depth--;
            if (S[i-1] == '(') ans += 1 << depth;
        }
    }
    return ans;
}

使括号有效的最小添加个数

int minAddToMakeValid(string S) {
    int bal = 0, ans = 0;
    for (char c : S) {
        bal += (c == '(') ? 1 : -1;
        if (bal == -1) {
            bal++;
            ans++;
        }
    }
    ans += bal;
    return ans;
}