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