301. Remove Invalid Parentheses.md

301. Remove Invalid Parentheses

思路

思路一、暴力BFS

由于要求去掉最少的字符，所以考虑用BFS（不能DFS）：把给定字符串入队，然后取出检测其是否合法，若合法就将其存放到结果数组res；不合法的话，对其进行遍历，依次穷举去掉每个括号然后得到一个新串，如果这个字符串之前没有遇到过（所以需要用一个set来记录出现过的字符串），将其入队。

注意：一旦res不为空，就说明上一轮循环已经找到了合法的串，再进行循环的话会继续去掉更多括号，所以没必要继续循环。

本方法存在大量重复计算，所以比较耗时。

思路二、DFS

注意到要求去掉最少的字符，所以返回的所有字符串的长度都是固定的（而且分别删除多少左右括号也是固定的）。而且我们可以提前把这个长度算出来，这样就可以使用DFS了。

为此，我们首先先统计多余的括号的数量，用left表示多余的左括号，right表示多余的右括号，一次遍历就可算出left和right，例

0 1 2 3 4 5 6 7
( ) ) ) ( ( ( )  

i = 0, left = 1, right = 0
i = 1, left = 0, right = 0
i = 2, left = 0, right = 1
i = 3, left = 0, right = 2
i = 4, left = 1, right = 2
i = 5, left = 2, right = 2
i = 6, left = 3, right = 2
i = 7, left = 2, right = 2

上例有两个多余的左括号，两个多余的右括号。

然后我们就可以使用DFS：

• 当left == 0 && right == 0时，判断是否合法，若合法则存入结果数组res中；
• 否则，需要进行递归。遍历当前字符串，如果当前字符为左括号且left > 0，那么表示可以删掉这个左括号，然后递归调用；右括号同理。

注意为了避免重复计算，我们用变量start表示当前递归开始的位置，遍历时只需从start开始就可以了而不需要每次都从头开始。而且，对于相邻的相同括号，只需要删除第一个，比如 "())"，这里有两个右括号，不管删第一个还是删第二个右括号都会得到 "()"，没有区别，所以只用算一次就行了。

相比于思路一，本思路避免了很多重复计算，因此高效很多。

C++

思路一

class Solution {
private:
    bool valid(const string &s){ // 判断字符串是否合法
        int cnt = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '(') cnt++;
            else if(s[i] == ')' && (--cnt < 0)) return false;
        }
        return cnt == 0;
    }
    
public:
    vector<string> removeInvalidParentheses(string s) {
        vector<string>res;
        queue<string>q; q.push(s);
        unordered_set<string>visited; visited.insert(s);

        while(!q.empty()){
            string ss = q.front(); q.pop();
            if(valid(ss)) res.push_back(ss);            
            else{
                if(!res.empty()) continue; // 在上一轮已经找到了最长的合法串, 接下来的肯定要短些
                // 穷举:删除每个括号
                for(int i = 0; i < ss.size(); i++){
                    if(ss[i] != '(' && ss[i] != ')') continue;
                    if(i > 0 && ss[i] == ss[i-1]) continue;
                    string subs = ss.substr(0, i) + ss.substr(i+1);
                    if(visited.find(subs) == visited.end()) {
                        q.push(subs);
                        visited.insert(subs);
                    }
                }
            }
        }
        
        return res;
    }
};

思路二

class Solution {
private:
    bool valid(const string &s){
        int cnt = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '(') cnt++;
            else if(s[i] == ')' && (--cnt < 0)) return false;
        }
        return cnt == 0;
    }
    
    void DFS(string s, int left, int right, int start, vector<string> &res){
        if(!left && !right){
            if(valid(s)) res.push_back(s);
            return;
        }
        for(int i = start; i < s.size(); i++){
            if(i > start && s[i] == s[i-1]) continue; // 去重
            
            if(left > 0 && s[i] == '(') 
                DFS(s.substr(0, i) + s.substr(i+1), left-1, right, i, res);
            else if(right > 0 && s[i] == ')')
                DFS(s.substr(0, i) + s.substr(i+1), left, right-1, i, res);
        }
    }
    
public:
    vector<string> removeInvalidParentheses(string s) {
        vector<string> res;
        
        int left = 0, right = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '(') left++;
            else if(s[i] == ')'){
                if(left > 0) left--;
                else right++;
            }
        }
        
        DFS(s, left, right, 0, res);
        return res;
    }
};