Remove Invalid Parentheses -- Leetcode

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 

)

.

Examples:

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]
      

基本思路为，广度优先搜索。

每层检验括号是否配对。

如果不配对，则顺序删除一个字符，进行下一层的判断。

在此基础上，进行优化。

1. 判断括号匹配时，只进行单向。 先从左到右，确保任何时刻，( 的数量>= )； 再从右到左，确保任何时候，) 的数量 >= (。 两都同时满足，则括号互相是匹配的。

2. 在扫描时，当上述条件不成立时，从左向右，偿试删除一个 ) ，取得一个新的字符串。 此时，条件满足，继续步骤1.

为了避免生成重复的结果，需要注意以下两种情况：

1. 字符删除位置，需要在上次操作的右面。

当删除2个位置的)时，会以不同的顺序生成重复的结果。

比如，先删除第一个，再删除第二； 先删除第二个，后删除第一个。 但此时生成的结果是一样的。

2. 如果上一个位置是)，当前位置也是)，需要跳过。

)))，因为连着的)))，删除任一个，得到的结果是一样的。所以要避免重复。

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        vector<string> ans;
        helper(ans, s, 0, 0, '(', ')');
        return ans;
    }
    
    void helper(vector<string>& ans, const string& s, int index, int remove_index, char leftp, char rightp) {
        int leftp_count = 0;
        for (int i=index; i<s.size(); i++) {
            if (s[i] == leftp)
                leftp_count ++;
            else if (s[i] == rightp)
                leftp_count --;
                
            if (leftp_count >= 0)
                continue;
            
            for (int j=remove_index; j<=i; j++) {
                if (s[j] == rightp && (j == remove_index || s[j-1] != rightp))
                    helper(ans, s.substr(0, j) + s.substr(j+1), i, j, leftp, rightp);
            }
            return;
        }
        
        if (leftp == '(') {
            helper(ans, string(s.rbegin(), s.rend()), 0, 0, rightp, leftp);
        } else {
            ans.push_back(string(s.rbegin(), s.rend()));
        }
    }
};
           

https://discuss.leetcode.com/topic/34875/easy-short-concise-and-fast-java-dfs-3-ms-solution