301. Remove Invalid Parentheses（去除最少数量得无效括号）——todo

红太狼 2023-02-13 11:59 26阅读 0赞

it’s hard to understand for me. I have to spend some time learning this solution.

删除无效括号的最小数目，以使输入字符串有效。返回所有可能的结果。

注意： 输入字符串可能包含括号(和之外的字母)。

范例1：

输入： “（）（））（）”  
输出： \[“（）（）（）”，“（（））（）”\]  
范例2：

输入： “（a）（））（）”  
输出： \[“（a）（）（）”，“（a（））（）”\]  
范例3：

输入： “）（”  
输出： \[“”\]

思路：

code：

//利用计数器记录（数量与） 是否匹配。
    class Solution { 
        private:
            vector<string> res;
            string p={ '(',')'};
            void helper(string& s, int si, int sj, int rev){ 
                int stn=0;
                for(int i=si;i<s.size();i++){ 
                    if(s[i]==p[rev]) stn++;
                    else if(s[i]==p[1-rev]) stn--;
                    if(stn<0){ 
                        for(int j=sj;j<=i;j++){ 
                            if(s[j]==p[1-rev] && (j==sj || s[j-1]!=p[1-rev])){ 
                                string t=s.substr(0,j)+s.substr(j+1);
                                helper(t, i, j, rev);
                            }
                        }
                        return ;
                    }
                }
                string rs=s;
                reverse(rs.begin(), rs.end());
                if(p[rev]=='('){ 
                    helper(rs, 0, 0, 1-rev);
                }else{ 
                    res.push_back(rs);
                }
            }    
        public:
            vector<string> removeInvalidParentheses(string s) { 
                res.clear();
                helper(s, 0, 0, 0);
                return res;
            }
        };