[数据结构与算法]Leetcode 第1天打卡 301. 删除无效的括号

题目：

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

解题思路：

合法的括号序列需满足：左=右 ；任一前缀中 左>=右

1.普通DFS
先求出最少需要删除几个左括号和右括号
然后就是普通的DFS：对于每个括号有删或不删两种状态
2.剪枝优化DFS
对于如“ ((()) ”可得到合法的方案：删除第一个左括号 得(())；删除第二个左括号 得(())；删除第三个左括号 得(())。在这里三步都做的重复工作，达到的效果是一样的，因此，我们可以人为规定删除顺序。对于连续的括号，可以考虑一次性删除k个，且删除的终点固定为右端点即可。这样对于上例 我们只需要看一种合法方案了，即删除第三个左括号 得(()) 对于连续的括号 复杂度将从2^k降到k。

class Solution {
public:
    vector<string> ans;//此时不会重复搜索 无重复方案 直接存即可
    //u其实为标记括号长度的,字符串s的索引， 便于返回
    void dfs(string &s, int u, string res, int cnt, int l, int r){//cnt为当前左-右的值 l为需要删除的左括号数量 r为右
        //cout<<res<<endl;
        if(u==s.size()){//当u与s.size()相等， 把res加入ans的数组中
            if(!cnt) ans.push_back(res);
            return;
        }
        if(s[u]=='('){//在合法的条件下考虑删除 对于连续的k个'(' 只需考虑一次性 删 i个(0<=i<=k) 则可从2^k降到 k
            int k = u;
            while (k < s.size() && s[k] == '(') k ++;//找到最后一个连续的'('的右边
            l -= k - u;//假设将这些连续的'('全部删除
            for (int i = k - u; i >= 0; i -- ) {//i为删除后的位置
            //i表示删除"("的个数，l>=表示可以继续删；
                if (l >= 0) dfs(s, k, res, cnt, l, r);//可删时
                res += '(', cnt ++, l ++ ;//此处是l<0，表示不可以删除那么多左括号，因此补回来；直到l>=0满足
            }
        }
        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 -- ) {//i为删除后的位置
                if (cnt >= 0 && r >= 0) dfs(s, k, res, cnt, l, r);//可删时  cnt >= 0表示当前左-右的值大于等于0 
                res += ')', cnt--, r++;
            }
        }
        else dfs(s,u+1,res + s[u],cnt,l,r);//遇到其他字符时，
    }
    vector<string> removeInvalidParentheses(string s) {
        int l = 0, r = 0;//l为当前左括号-右括号的值 ,即是要删除的左括号的值;r为需要删掉的右括号的值
        for(auto v : s){
            if(v=='(') l++;//左括号时，l+1
            else if(v==')'){//右括号时，
                if(l <= 0) r++;//此时无效 右括号 必删
                else l--;//右括号+1 则左-右的值需要--   
            }  
        }
        dfs(s,0,"",0,l,r);
        return ans;
    }
};