• 力扣(LeetCode)301. 删除无效的括号(2022.10.29)


    给你一个由若干括号和字母组成的字符串 s ,删除最小数量的无效括号,使得输入的字符串有效。

    返回所有可能的结果。答案可以按 任意顺序 返回。

    示例 1:

    输入:s = “()())()”
    输出:[“(())()”,“()()()”]

    示例 2:

    输入:s = “(a)())()”
    输出:[“(a())()”,“(a)()()”]

    示例 3:

    输入:s = “)(”
    输出:[“”]

    提示:

    1 <= s.length <= 25
    s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成
    s 中至多含 20 个括号

    来源:力扣(LeetCode)
    链接:https://leetcode.cn/problems/remove-invalid-parentheses

    方法一:回溯+剪枝

    C++提交内容:

    class Solution {
    public:
        vector<string> res;
        vector<string> removeInvalidParentheses(string s) {
            int lremove = 0;
            int rremove = 0;
    
            for (char c : s) {
                if (c == '(') {
                    lremove++;
                } else if (c == ')') {
                    if (lremove == 0) {
                        rremove++;
                    } else {
                        lremove--;
                    }
                }
            }
            helper(s, 0, lremove, rremove);
            return res;
        }
    
        void helper(string str, int start, int lremove, int rremove) {
            if (lremove == 0 && rremove == 0) {
                if (isValid(str)) {
                    res.push_back(str);
                }
                return;
            }
            for (int i = start; i < str.size(); i++) {
                if (i != start && str[i] == str[i - 1]) {
                    continue;
                }
                // 如果剩余的字符无法满足去掉的数量要求,直接返回
                if (lremove + rremove > str.size() - i) {
                    return;
                } 
                // 尝试去掉一个左括号
                if (lremove > 0 && str[i] == '(') {
                    helper(str.substr(0, i) + str.substr(i + 1), i, lremove - 1, rremove);
                }
                // 尝试去掉一个右括号
                if (rremove > 0 && str[i] == ')') {
                    helper(str.substr(0, i) + str.substr(i + 1), i, lremove, rremove - 1);
                }
            }
        }
    
        inline bool isValid(const string & str) {
            int cnt = 0;
    
            for (int i = 0; i < str.size(); i++) {
                if (str[i] == '(') {
                    cnt++;
                } else if (str[i] == ')') {
                    cnt--;
                    if (cnt < 0) {
                        return false;
                    }
                }
            }
    
            return cnt == 0;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
  • 相关阅读:
    std::this_thread
    老卫带你学---leetcode刷题(344. 反转字符串)
    ovirt4.5-engine 安装
    前端周刊第二十三期
    边缘计算(一):EdgeNeXt,面向移动开发的CNN-Transformer混合架构
    设计模式之单例模式(1)
    Rust常用特型之Drop特型
    MyBatis多条件查询、动态SQL、多表操作、注解开发详细教程
    短视频内容创作:内容发给谁?为什么发?发什么?以什么形式发?
    java计算机毕业设计口红专卖网站源码+mysql数据库+系统+lw文档+部署
  • 原文地址:https://blog.csdn.net/ChaoYue_miku/article/details/127594251