题目

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。

示例：

输入：s = "()())()"
输出：["(())()","()()()"]

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

输入：s = ")("
输出：[""]

解答 & 代码

解法一：递归回溯 + 剪枝

class Solution {
private:
    string originS;     // 原字符串 s
    int strLen;         // 原字符串 s 的长度
    int resultLen;      // 删除最小数量的无效括号后，剩余字符串的长度
    // maxScore 用于剪枝，即最终答案字符串中括号对数的最大值，若递归过程中 score 超出 [0, maxScore] 则剪枝
    int maxScore;       // 搜索过程中可能出现的最大得分（= 原字符串 s 中左括号数量、右括号数量的最小值）
    unordered_set<string> result;   // 用哈希表存储所有可能的结果，以达到去重的目的
    /* 递归回溯搜索 + 剪枝
     * param idx: 当前遍历到原字符串 s 的下标
     * param curS: 当前得到的结果字符串（遍历 s[idx] 之前形成的结果字符串）
     * param leftDeleteNum: 当前剩余应删除的左括号的数目
     * param rightDeleteNum: 当前剩余应删除的右括号的数目
     * param score: 当前的得分。若结果字符串 curS 保留一个左括号，则 score + 1;
                                若结果字符串 curS 保留一个右括号，则 score - 1
     */
    void dfs(int idx, string curS, int leftDeleteNum, int rightDeleteNum, int score)
    {
        // 递归结束条件 1：如果剩余应删除的左括号数目 or 右括号数目 < 0 
        //             或者 score 超出范围 [0, maxScore] 则剪枝：
        //             - score < 0 说明 curS 中右括号多于左括号；
        //            - score > maxScore 说明保留的左括号数超过了应保留的括号对数的最大数目
        if(leftDeleteNum < 0 || rightDeleteNum < 0 || score < 0 || score > maxScore)
            return;
        // 如果剩余应删除的左括号数目 and 右括号数目都为 0
        // 若当前结果字符串 curS 的长度 等于 删除最小数量的无效括号后剩余字符串的长度
        // 则，将当前结果字符串 curS 插入哈希表
        if(leftDeleteNum == 0 && rightDeleteNum == 0)
            if(curS.size() == resultLen)
                result.insert(curS);
        // 递归结束条件 2：如果当前已遍历完字符串 s，则结束递归
        if(idx == strLen)
            return;
        // 当前遍历到的字符串
        char ch = originS[idx];
        if(ch == '(')
        {
            // 保留当前的左括号，则剩余应删的左括号数目不变，score + 1
            dfs(idx + 1, curS + ch, leftDeleteNum, rightDeleteNum, score + 1);
            // 删除当前的左括号，则剩余应删的左括号数目 - 1，score 不变
            dfs(idx + 1, curS, leftDeleteNum - 1, rightDeleteNum, score);
        }
        else if(ch == ')')
        {
            // 保留当前的右括号，则剩余应删的右括号数目不变，score - 1
            dfs(idx + 1, curS + ch, leftDeleteNum, rightDeleteNum, score - 1);
            // 删除当前的右括号，则剩余应删的右括号数目 - 1，score 不变
            dfs(idx + 1, curS, leftDeleteNum, rightDeleteNum - 1, score);
        }
        else    // 当前字符不是括号，则保留
            dfs(idx + 1, curS + ch , leftDeleteNum, rightDeleteNum, score);
    }
public:
    vector<string> removeInvalidParentheses(string s) {
        originS = s;                // 原字符串 s
        strLen = s.size();          // 原字符串 s 的长度
        int leftDeleteNum = 0;      // 最少应该删除的左括号数量
        int rightDeleteNum = 0;     // 最少应该删除的右括号数量
        int leftBracketNum = 0;     // 原字符串 s 中的左括号数
        int rightBracketNum = 0;    // 原字符串 s 中的右括号数
        // 遍历字符串 s，统计得到以上 4 个变量的值
        for(int i = 0; i < s.size(); ++i)
        {
            if(s[i] == '(')
            {
                ++leftDeleteNum;
                ++leftBracketNum;
            }
            else if(s[i] == ')')
            {
                if(leftDeleteNum != 0)
                    --leftDeleteNum;
                else
                    ++rightDeleteNum;
                ++rightBracketNum;
            }
        }
        // 最后返回的结果字符串的长度，即 删除最小数量的无效括号后 剩余字符串的长度
        resultLen = s.size() - leftDeleteNum - rightDeleteNum;
        // 搜索过程中可能出现的合法的最大得分，
        // = 原字符串 s 中左括号数量、右括号数量的最小值，即最终答案字符串中括号对数的最大值
        // 最大得分为：合法的左括号先全部出现在左边，此时 score 达到最大
        // 如过 score 超过 maxScore，说明保留的左括号数超出上限了，剪枝
        // 因此，maxScore 其实是 score 的上界，用于剪枝
        maxScore = min(leftBracketNum, rightBracketNum);
        // 递归回溯
        dfs(0, "", leftDeleteNum, rightDeleteNum, 0);
        // 将哈希表中的结果存储到数组中，并返回
        vector<string> resultList;
        for(auto it = result.begin(); it != result.end(); ++it)
            resultList.push_back(*it);
        return resultList;
    }
};

复杂度分析：设字符串 s 长为 N

时间复杂度：
- 预处理：计算 resultLen 和 maxScore 的时间复杂度 O(N)
- 每个位置都有两个选择，保留字符 or 删除字符，搜索所有方案的时间复杂度 (即每个字符串都有个子序列)。同时，搜索过程中会产生新的字符串，长度最大为 O(N)。因此整体时间复杂度
空间复杂度：递归栈深度 = 字符串长度，且每次递归调用都要复制一次字符串，因此空间复杂度

执行结果：

执行结果：通过
执行用时：8 ms, 在所有 C++ 提交中击败了 58.68% 的用户
内存消耗：13 MB, 在所有 C++ 提交中击败了 41.05% 的用户

解法二：BFS 广度优先搜索

题目中要求最少删除，这样的描述正是广度优先搜索算法应用的场景，并且题目也要求我们输出所有的结果。我们在进行广度优先搜索时每一轮删除字符串中的 1 个括号，直到出现合法匹配的字符串为止，此时进行轮转的次数即为最少需要删除括号的个数。

class Solution {
private:
    bool isValid(string str)
    {
        int score = 0;
        for(int i = 0; i < str.size(); ++i)
        {
            if(str[i] == '(')
                ++score;
            if(str[i] == ')')
            {
                --score;
                if(score < 0)
                    return false;
            }
        }
        return score == 0;
    }
public:
    vector<string> removeInvalidParentheses(string s) {
        vector<string> result;                // 结果数组
        unordered_set<string> curStrsMap;    // 上一轮的搜索结果
        curStrsMap.insert(s);                // 初始时插入 s
        // BFS 广度优先搜索
        while(true)
        {
            // 1. 遍历上一轮的搜索结果，逐个判断是否存在合法的结果，如果存在就插入到结果数组中
            // 判断字符串合法是看括号对是否匹配
            for(auto it = curStrsMap.begin(); it != curStrsMap.end(); ++it)
            {
                if(isValid(*it))
                    result.push_back(*it);
            }
            // 如果已经出现了合法结果，则当前结果就是删除最少的无效括号后的有效字符串，就是答案
            if(result.size() > 0)
                return result;        // 直接返回
            unordered_set<string> nextStrsMap;    // 记录这一轮的搜索结果
            // 2. 遍历上一轮的搜索结果，尝试删除任意位置上的一个括号，删除后的结果都保存在 nextStrMap
            for(auto it = curStrsMap.begin(); it != curStrsMap.end(); ++it)
            {
                string curStr = *it;
                for(int i = 0; i < curStr.size(); ++i)
                {
                    char ch = curStr[i];
                    if(ch == '(' || ch == ')')
                        nextStrsMap.insert(curStr.substr(0, i) + curStr.substr(i + 1, curStr.size() - i - 1));
                }
            }
            curStrsMap = nextStrsMap; 
        }
    }
};

复杂度分析：设字符串 s 长为 N

时间复杂度：
空间复杂度：在进行第 i 轮迭代时，会从原始字符串中删除 i 个括号，因此第 i 轮迭代产生的字符串最多有个，当 i = n/2 时组合数最大，此时迭代生成的字符串个数最多，因此空间复杂度为

执行结果：

执行结果：通过
执行用时：60 ms, 在所有 C++ 提交中击败了 36.33% 的用户
内存消耗：14.9 MB, 在所有 C++ 提交中击败了 29.49% 的用户

hot 100

[困难] 301. 删除无效的括号

题目

解答 & 代码

解法一：递归回溯 + 剪枝

解法二：BFS 广度优先搜索