301. Remove Invalid Parentheses

Link

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 ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

Solution

這題用BFS，但怎麼想到的不是很清楚。或許接觸多點BFS的題目再來思考其通則。

邏輯是列舉所有可能。包含刪除一個左/右括號到多個左/右括號。然後判斷是否valid。

透過BFS的好處是可以先找到最小的刪除次數，一旦找到就只要把同層valid的放入結果並回傳，反之就往下一層前進，再刪除一個左/右括號，並看看是否合法。

時間複雜度是: 加總每層的計算次數 沒刪除任何東西(level 0) : n , 其中n為input長度，為了判斷n是否valid，要花O(n) 刪除一個 (level 1) : (n -1) * $C(n,1)$ , 其中(n-1)是判斷valid的複雜度，然後 $C(n,1)$ 是所有可能數 刪除二個 (level 2) : (n -2) * $C(n,2)$ , 其中(n-2)是判斷valid的複雜度，然後 $C(n,2)$ 是所有可能數 .... 刪除n-1個 (level n-1) : (n -(n-1)) * $C(n,n-1)$ 加總起來: $TimeComplexity = n + (n-1)*C(n,1) + (n-2)*C(n,2) + ... + 1 *C(n,n-1) = n * 2^n-1 = O(n*2^n)$

    public List<String> removeInvalidParentheses(String s) {
        List<String> ret = new ArrayList<>();
        boolean isFound = false;
        Queue<String> queue = new LinkedList<>();
        HashSet<String> visted = new HashSet<>();
        queue.add(s);
        visted.add(s);
        while(!queue.isEmpty()){
            String toBeTest = queue.poll();
            
            if(isValid(toBeTest)){
                isFound = true;
                ret.add(toBeTest);
            }
            
            if(isFound){
                continue;
            }
            
            //shorten the toBeTest and put it into queue
            for(int i = 0; i < toBeTest.length(); i++){
                char c = toBeTest.charAt(i);
                if(c == '(' || c == ')'){
                    String newCandidate = toBeTest.substring(0,i) + toBeTest.substring(i+1);
                    if(!visted.contains(newCandidate)) {
                        queue.add(newCandidate);
                        visted.add(newCandidate);
                    }
                }
            }
        }
        return ret;
    }
    
    public boolean isValid(String input){
        int count = 0;
        for(int i = 0 ; i < input.length(); i++){
            if(input.charAt(i) == '('){
                count++;
            }else if(input.charAt(i) == ')'){
                if(count == 0){
                    return false;
                }
                count--;
            }  
        }
        return count == 0;
    }