二刷301. Remove Invalid Parenthese

一刷BFS,二刷DFS快很多

edge case: s = "" 不能返回空list, 要返回[""].
先统计不合法的(, )数目l, r， 然后开始dfs搜索。helper函数要避免duplicate和找到最少，避免duplicate靠的是check if (i > start && s.charAt(i) == s.charAt(i - 1)) 比如有两个连续的)删去都能得到合法结果，我们只考虑删去第一个)的情况来避免重复。 还有要先删多余的)，因为到最后如果你得到)(这种结果其实是无效的，一开始就可以删去多余的右括号来减少不必要的尝试。

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        if (s == null){
            return res;
        }
        if (s.length() == 0){
            res.add("");
            return res;
        }
        int l = 0;
        int r = 0;
        for (int i = 0; i < s.length(); i++){
            if (s.charAt(i) == '('){
                l++;
            }
            if (l == 0 && s.charAt(i) == ')'){
                r++;
            } else if (s.charAt(i) == ')'){
                l--;
            }
        }
        dfs(res, s, 0, l, r);
        return res;
    }
    
    private void dfs(List<String> res, String s, int start, int l, int r){
        if (l == 0 && r == 0){
            if (isValid(s)){
                res.add(s);
                return;
            }
        }
        for (int i = start; i < s.length(); i++){
            if (i > start && s.charAt(i) == s.charAt(i - 1)){
                continue;
            }
            String str = s.substring(0, i) + s.substring(i+1);   
            if (s.charAt(i) == ')' && r > 0){
                dfs(res, str, i, l, r - 1);
            } else if (s.charAt(i) == '(' && l > 0){
                dfs(res, str, i, l - 1, r);
            }
        }
    }
    
    private boolean isValid(String s){
        int count = 0;
        for (char c : s.toCharArray()){
            if (c == '('){
                count++;
            } else if (c == ')'){
                if (count == 0){
                    return false;
                }
                count--;
            } else {
                continue;
            }
        }
        return count == 0;
    }
}