AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 吐槽
  • App
  • 登录/注册

LeetCode 301. 删除无效的括号    原题链接    困难

作者: 作者的头像   gcc7 ,  2022-11-25 13:14:38 ,  所有人可见 ,  阅读 91


0


参考文献

ref

合法括号序列的判断条件:
1.左右括号数量相同
2.任意一个前缀中,左括号数量 >= 右括号数量

C++ 代码

class Solution {
public:
    // 计算需要删除的左括号数量l,需要删除的右括号数量r
    // 利用上述结论提前剪枝
    // 以及需要避免重复,即 ((( 这几个左括号删除一个结果都一样,因此需要枚举删除的数量

    vector<string> res;
    vector<string> removeInvalidParentheses(string s) {
        int l = 0, r = 0;
        for(char c : s){
            if(c == '(')l++;
            if(l==0 && c == ')')r++;
            else if(c == ')')l--;
        }
        // cout << l << "," << r << endl;
        dfs(s, 0, "", 0, l, r);
        return res;
    }

    // s:原字符串,u:当前搜索到的字符串下标,path:当前的结果字符串
    // cnt: 左括号减右括号的值;l:剩余左括号的数量;r:剩余右括号的数量
    void dfs(string s, int u, string path, int cnt, int l, int r){
        if(u == s.size()){
            if(!cnt){
                res.push_back(path);
            }
            return;
        }

        if(s[u]!='(' && s[u]!=')')dfs(s, u+1, path+s[u], cnt, l, r);
        else if(s[u] == '('){
            // 计算连续的(数量,然后枚举删除几个
            int k = u;
            while(k<s.size() && s[k]=='(')k++;
            l -= k-u; // 先假设一次性删除完连续的左括号
            for(int i=k-u; i>=0; i--){
                if(l>=0)dfs(s, k, path, cnt, l, r);
                // 每次再补回来一个 (
                l++, cnt++;
                path += '(';
            }
        } else if(s[u] == ')'){
            int k = u;
            while(k<s.size() && s[k]==')')k++;
            r -= k-u;
            // 每次再补回来一个 )
            for(int i=k-u; i>=0; i--){
                // 需要满足 左括号数量大于右括号,且还可以删除右括号
                if(cnt >=0 && r>=0)dfs(s, k, path, cnt, l, r);
                r++, cnt--;
                path += ')';
            }
        }
    }
};

0 评论

你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息