Remove Invalid Parentheses

这道题DFS和BFS都可以解决, 时间复杂度为2^

解法一(DFS)

这道题暴力穷举, 对于每一个左右括号, 都有"留"和"不留"两个选择,

在dfs的时候, 在第一次的时候保留左括号, 这样第一次得到的解一定是最多左括号, 一定是最长的.

public class Solution {
    static int maxL = Integer.MIN_VALUE;
    public List<String> ans = new ArrayList<String>();
    public List<String> removeInvalidParentheses(String s) {
        dfs(s, "",  0, 0);
        if(ans.isEmpty()) ans.add("");
        return ans;
    }
    //curleft represent remain left pathreses to match
    //maxLeft represent histoy
    public void dfs(String s, String cur, int curLeft, int maxLeft){
        if(s.length()==0){
            if(curLeft==0 && cur.length()!=0){
                maxL = Math.max(maxLeft, maxL);
                if(maxLeft==maxL && !ans.contains(cur)) 
                    //key:"()()()","()()()" duplicate might contains
                    ans.add(cur);
            }
            return;
        }

        char c = s.charAt(0);
        if(c=='('){
            dfs(s.substring(1),  cur+c, curLeft+1, maxLeft+1);
            dfs(s.substring(1),  cur, curLeft, maxLeft);
        }
        else if(c==')'){
            if(curLeft>0)
                dfs(s.substring(1),  cur+c, curLeft-1, maxLeft);
            dfs(s.substring(1),  cur, curLeft, maxLeft);
        }
        else
            dfs(s.substring(1),  cur+c, curLeft, maxLeft);
        return;
    }
}

解法二(BFS)

这个不推荐在面试时使用.

通过BFS搜索解决. 对原始字符串"()())()", 尝试移除一个"(" 或")" 括号, 加入queue,

BFS每加深一层, 多移除一个括号. 当第一次BFS看到valid的"()()()"的字符串为最长的

看到最长的以后搜索完本层退出.

public class Solution {

    public List<String> removeInvalidParentheses(String s) {
        List<String> ans = new ArrayList<String>();
        if(s==null || s.length()==0){
            ans.add("");
            return ans;
        }
        HashSet<String> visited = new HashSet<String>();
        Queue<String> queue = new LinkedList<String>();
        queue.add(s);visited.add(s);
        boolean found = false;//key point
        while(!queue.isEmpty()){
            String cur = queue.poll();
            if(isValid(cur)){
                ans.add(cur);
                found = true; //key point
            }
            if(found) continue; // guarantee long path, once ()() is valid, () won't be consider
            char[] array = cur.toCharArray();
            for(int i=0;i<array.length;i++){
                if(array[i] =='(' || array[i]==')'){
                    String tmp = cur.substring(0, i) + cur.substring(i+1);
                    if(!visited.contains(tmp)){
                        queue.offer(tmp);
                        visited.add(tmp);
                    }
                }
            }
        }
        if(ans.size()==0) ans.add("");//key point
        return ans;
    }

    public boolean isValid(String s){
        int count = 0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='(') count++;
            if(s.charAt(i)==')') count--;
            if(count<0) return false;
        }
        return count==0;
    }

    /*
    However, it does it implicitly. For a string of parentheses to be valid, its number of parentheses should be even. And at any time, strings in queue will only differ in length of 1 (this is the implicit control). When we find "()()" to be valid, both "()" and "" have not been added to queue yet and all the shorter strings are of length of 3, which must be invalid.

    */
}