Hard超高頻
看了很久Discussion里面最高票的答案，一直沒看懂。晚上開始看后面的答案，發(fā)現(xiàn)了一個BFS的方法比較好理解。其實(shí)這個方法的思路很brute force, 就是每次我們刪掉一個括號（左或右），檢查剩下的string是不是valid. 每次選擇一個位置，就只需要遍歷整個string用O(N)完成。一開始這個方法聽起來會耗費(fèi)很多時間，但因?yàn)槲覀円皇菚靡粋€set來記錄訪問過的string(也同時保證了答案沒有duplicate），二是只要刪著刪著找到一個需要刪掉括號符號的最小個數(shù)我們就不用繼續(xù)了，因?yàn)檫@個問題本來就是讓我們求出需要刪掉最少個數(shù)invalid parentheses的解。

我們用一個boolean found來記錄是不是找到了那個刪除最少非法括弧后第一個出現(xiàn)的valid string. 如果說找到了，我們就加到答案里，并且found = true. 一開始我疑惑為什么循環(huán)末尾我們不把found reset成false呢。后來一想，這個BFS每一層的元素都是長度相同的string，也就是上一層選擇某個位置的字符刪掉后剩下的那些字符。所以當(dāng)我們found = true后，我們其實(shí)就知道不用再繼續(xù)找下面的層了，也就是不需要再往queue里offer東西。就只需要把當(dāng)前queue里剩下的元素繼續(xù)check isValid完就好。這也是為什么我們不能找到一個就break出來。因?yàn)槿绻@一層還有其他string isValid, 我們得全部加到res里面。

這個isValid method寫得也比較直接，就是用一個count 來計(jì)算(的個數(shù)，遇到)就想當(dāng)于匹配一個，所以count --. 這樣如果我們遍歷到)時count <= 0那肯定invalid. 這樣最后再check一下count == 0？就好了。

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        if (s == null){
            return res;
        }
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        visited.add(s);
        queue.offer(s);
        boolean found = false;
        while (!queue.isEmpty()){
            String curt = queue.poll();
            if (isValid(curt)){
                res.add(curt);
                found = true;
            }
            if (found){
                continue;
            }
            for (int i = 0; i < curt.length(); i++){
                if (curt.charAt(i) != '(' && curt.charAt(i) != ')'){
                    continue;
                }
                String next = curt.substring(0, i) + curt.substring(i+1);
                if (!visited.contains(next)){
                    queue.offer(next);
                    visited.add(next);
                }
            }
        }
        return res;
    }
    
    private boolean isValid(String s){
        int count = 0;
        for (char c : s.toCharArray()){
            if (c == '('){
                count++;
            } else if (c == ')'){
                if (count == 0){
                    return false;
                } else {
                    count--;
                }
            }
        }
        return count == 0;
    }
}