题目描述

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

题意：删除最少的括号使得剩下来的括号合法，返回所有的最长合法序列。

算法1

(搜索+剪枝)

题解：首先我们要知道删除多少左括号和右括号，我们从左到右遍历一遍，如果遇到左括号，那么l ++代表当前未匹配的左括号，如果遇到右括号并且当前未匹配的左括号个数大于0，那么l --，说明当前右括号前面有与之匹配的左括号，如果未匹配的左括号个数等于0，说明当前这个括号是不合法的，r ++，最后l代表还没有匹配的左括号个数，也就是我们需要删除的个数。

接下来就是搜索+剪枝了。dfs函数参数分别为当前字符串、当前字符串已经遍历过的字符，当前字符串还需要删除多少个左括号和右括号。当不需要再删除括号的时候，判断当前字符串是否合法，如果合法就加入答案。

在扫描字符串时，如果遇到非括号字符直接跳过，遇到左右括号的时候如果还可以删除当前括号，那么就删除并递归求解。

剪枝策略1：多个连续相同的括号，我们只删除最左边的那个进行搜索，因为删除后序的括号得到的字符串也是一样的。

剪枝策略2:如果剩余字符数字已经小于还需要删除的字符个数，剪枝。（因为有非括号字符，所以还可以标记剩余的左括号和右括号个数是否小于当前要删除的个数，得到更早的剪枝）

C++ 代码

class Solution {
public:
    vector<string> res;
    vector<string> removeInvalidParentheses(string s) {
        int l = 0,r = 0,n = s.length();
        for(int i = 0 ; i < n ; i ++)
        {
            if(s[i] == '(') l ++;
            if(l == 0 && s[i] == ')') r ++;
            else if(s[i] == ')') l --;
        }
        dfs(s,0,l,r);
        return res;
    }
    bool check(string s)
    {
        int cnt = 0,n = s.length();
        for(int i = 0 ; i < n ; i ++)
        {
            if(s[i] =='(') cnt ++;
            else if(s[i] == ')') cnt --;
            if(cnt < 0) return false;
        }
        return cnt == 0;
    }
    void dfs(string s,int u,int l,int r)
    {
        if(l == 0 && r == 0)
        {
            if(check(s)) res.push_back(s);
            return;
        }
        int n = s.length();
        for(int i = u ; i < n ; i ++)
        {
            if(s[i] != '(' && s[i] != ')') continue;
            if(i == u || s[i] != s[i - 1])
            {
                string cur = s;
                cur.erase(i,1);
                if(s[i] == '(' && l > 0) dfs(cur,i,l - 1,r);
                else if(s[i] == ')' && r > 0) dfs(cur,i,l,r - 1);
            }
        }
    }
};