Leetcode 301 - study code - Remove Invalid Parentheses

Leetcode301_studyCode.cpp

/*
Feb. 7, 2018
Analysis of the algorithm
Leetcode 301: Remove Invalid Parentheses

Analysis is from my favorite coding blog: http://blog.csdn.net/qq508618087/article/details/50408894

I like to rewrite the notes in Chinese, and then write an English version afterwards. 

There are two cases to handle, one is to have unmatched close bracket. We should handle
unmatched close bracket once it is found. And the second case is extra open brackets which 
can be treated as unmatched clse bracket if the iteration is from back to the first. 

Let us go over the first case called unmatched close bracket. 

')'的个数多于左括号

遍历一个字符串，在任何时候如果')'的个数多于左括号，则说明从开始到现在位置必然可以删除一个')'．

多个')'删除哪一个

这段子串可能包含多个')'，删除哪一个呢？当然删除任何一个都可以．例如对于()())()，从开头到
s[4]位置构成的子串 "()())", 多了一个右括号. 

这个子串有三个右括号，但是只会产生２个结果，也就是会有一个重复值．所以在删除括号的时候，为
保证不会产生重复值，需要记录一个最后删除的位置，这样可以使得在接下来删除的时候只删除这个位置
之后的值．这样我们可以使得当前这一段子串不再包含多余的右括号了．这样我们可以删除了一个右括号
之后合法的子串与后面还没有检查过的子串组成一个新的字符串重新开始检查．直到不再含有非法的右括号．

包含了多余的左括号

还有一种情况是包含了多余的左括号，一种直观的方法是从右向左再按照上面的方法处理一遍左括号．
但是将数组逆置之后就可以重用上面的算法了．

所以总的思路就是先对字符串进行处理使得其不再含有非法右括号，然后将其翻转以后再检查是否含有非法的
左括号．最后左右括号都检查完之后都合法就是我们要的答案了．

时间复杂度应该是O(n^2)，但是对与这道题来说，这是一个非常高效的方法了，运行时间０ms，比绝大多数
算法都要高效．
*/
class Solution {  
public:  
    void DFS(string s, char ch, int last)  
    {  
        for(int i = 0, cnt = 0; i < s.size(); i++)  
        {  
            if(s[i]=='(' || s[i]==')') s[i]==ch?cnt++:cnt--;  
            if(cnt <= 0) continue;  
            
            for(int j = last; j <= i; j++)  
            {  
                if(s[j] == ch && (j ==last || s[j-1]!= ch))  
                    DFS(s.substr(0, j)+s.substr(j+1), ch, j);  
            }  
            
            return;  
        }  
        
        reverse(s.begin(), s.end());  
        if(ch == ')') return DFS(s, '(', 0);  
        ans.push_back(s);  
    }  
      
    vector<string> removeInvalidParentheses(string s) {  
        DFS(s, ')', 0);  
        return ans;  
    }  
    
private:  
    vector<string> ans;  
};