Remove Invalid Parentheses（C++删除无效的括号）

深碍√TFBOYSˉ_ 2022-09-07 03:46 114阅读 0赞

（1）回溯

class Solution {
    private:
        vector<string> v;
        unordered_set<string> st;
    public:
        void helper(string &s,string p,int index,int left,int right,int left_,int right_) {
            if(index==s.length()) {
                if(left_==0 && right_==0) st.insert(p);
                return;
            }
            
            char c=s[index];
            if(c=='(' && left_>0) helper(s,p,index+1,left,right,left_-1,right_);
            else if(c==')' && right_>0) helper(s,p,index+1,left,right,left_,right_-1);
            
            p.push_back(c);
            if(c!='(' && c!=')') helper(s,p,index+1,left,right,left_,right_);
            else if(c=='(') helper(s,p,index+1,left+1,right,left_,right_);
            else if(left>right) helper(s,p,index+1,left,right+1,left_,right_);
            p.pop_back();
            return;
        }
        
        vector<string> removeInvalidParentheses(string s) {
            int left=0,right=0;
            for(int i=0;i<s.length();i++) {
                if(s[i]=='(') left++;
                else if(s[i]==')') {
                    if(left==0) right++;
                    else left--;
                }
            }
            
            string p="";
            helper(s,p,0,0,0,left,right);
            for(auto &&w:st)
                v.push_back(w);
            return v;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，114人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_回溯_困难_301.删除无效的括号

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符

ゝ一纸荒年。/ 2023年10月06日 22:47/ 0 赞/ 18 阅读

相关 301. 删除无效的括号（高频题）

301. 删除无效的括号解题思路代码解题思路要用回溯算法，一刷2021/3/19，没有完全弄明白 --------------------

- 日理万妓/ 2023年10月04日 08:47/ 0 赞/ 9 阅读

相关 Java：移除无效的括号

一、题目给你一个由 ‘(’、’)’ 和小写字母组成的字符串 s。你需要从字符串中删除最少数目的 ‘(’ 或者 ‘)’ （可以删除任意位置的括号)，使得剩下的「括号字

- 日理万妓/ 2023年01月14日 14:56/ 0 赞/ 114 阅读

相关 LeetCode:1021. Remove Outermost Parentheses删除最外层的括号(C语言)

题目描述：有效括号字符串为空 ("")、"(" + A + “)” 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"

小鱼儿/ 2022年12月22日 00:46/ 0 赞/ 122 阅读

相关 Minimum Remove to Make Valid Parentheses（C++移除无效的括号）

解题思路：（1）从前往后，从后往前，记录balance的值 class Solution { public: string minRemo

小鱼儿/ 2022年11月07日 05:51/ 0 赞/ 27 阅读

相关 Set iterator.remove()；无效

问题背景使用的是`HashSet`，对象用了lombok的`@Data`注解，这里面重写过`hashCode`和`equals`。来看现象，首先看我这里有

爱被打了一巴掌/ 2022年09月11日 08:23/ 0 赞/ 154 阅读

相关 Remove Invalid Parentheses（C++删除无效的括号）

（1）回溯 class Solution { private: vector<string> v; unordered_

深碍√TFBOYSˉ_/ 2022年09月07日 03:46/ 0 赞/ 115 阅读

相关 Leecode 301. 删除无效的括号——Leecode每日一题系列

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

缺乏、安全感/ 2022年08月28日 01:43/ 0 赞/ 210 阅读

相关 leetcode 301. Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid

迈不过友情╰/ 2022年08月20日 02:25/ 0 赞/ 19 阅读

相关 LeetCode301——删除无效的括号

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCod

怼烎@/ 2022年01月23日 01:41/ 0 赞/ 392 阅读