@@ -0,0 +1,1868 @@
+package leetcode301_310;%0A%0Aimport java.util.*;%0A%0A/**Remove the minimum number of invalid parentheses in order to make the input string valid.%0A Return all possible results.%0A Note: The input string may contain letters other than the parentheses ( and ).%0A%0A Examples:%0A %22()())()%22 -%3E %5B%22()()()%22, %22(())()%22%5D%0A %22(a)())()%22 -%3E %5B%22(a)()()%22, %22(a())()%22%5D%0A %22)(%22 -%3E %5B%22%22%5D%0A * Created by eugene on 16/6/2.%0A */%0Apublic class RemoveInvalidParentheses %7B%0A%0A    /**https://leetcode.com/discuss/72208/easiest-9ms-java-solution%0A     * DFS, %E5%89%AA%E6%9E%9D%E6%9D%A1%E4%BB%B6%E8%BE%83%E5%A4%9A,%E6%B6%89%E5%8F%8ArmL(%E5%BE%85%E7%A7%BB%E9%99%A4%E5%B7%A6%E6%8B%AC%E5%8F%B7%E6%95%B0),rmR(%E5%BE%85%E7%A7%BB%E9%99%A4%E5%8F%B3%E6%8B%AC%E5%8F%B7%E6%95%B0),open(%E5%B0%9A%E6%9C%AA%E5%8C%B9%E9%85%8D%E7%9A%84%E5%B7%A6%E6%8B%AC%E5%8F%B7%E6%95%B0)%0A     * @param s%0A     * @return%0A     */%0A    public List%3CString%3E removeInvalidParentheses(String s) %7B%0A        Set%3CString%3E res = new HashSet%3C%3E();  //%E5%8E%BB%E9%99%A4%E9%87%8D%E5%A4%8D%0A        int rmL = 0, rmR = 0;%0A        for(int i = 0; i %3C s.length(); i++) %7B   //%E6%B3%A8%E6%84%8F%E8%AE%A1%E7%AE%97rmL%E4%B8%8ErmR%E7%9A%84%E5%B7%A7%E5%A6%99%E6%96%B9%E6%B3%95%0A            if(s.charAt(i)=='(') rmL++;%0A            else if(s.charAt(i)==')') %7B%0A                if(rmL!=0) rmL--;%0A                else rmR++;%0A            %7D%0A        %7D%0A        DFS(res, s, 0, rmL, rmR, 0, new StringBuilder());%0A        return new ArrayList%3C%3E(res);%0A    %7D%0A    public void DFS(Set%3CString%3E res, String s, int start, int rmL, int rmR, int open, StringBuilder sb) %7B%0A        if(start==s.length() && rmL==0 && rmR==0 && open==0) %7B%0A            res.add(sb.toString());%0A            return;%0A        %7D%0A        if(start==s.length() %7C%7C rmL%3C0 %7C%7C rmR%3C0 %7C%7C open%3C0) return;%0A        char c = s.charAt(start);%0A        int len = sb.length();%0A        if(c=='(') %7B%0A            DFS(res, s, start+1, rmL-1, rmR, open, sb);%0A            DFS(res, s, start+1, rmL, rmR, open+1, sb.append(c));%0A        %7D else if(c==')') %7B%0A            DFS(res, s, start+1, rmL, rmR-1, open, sb);%0A            DFS(res, s, start+1, rmL, rmR, open-1, sb.append(c));%0A        %7D else %7B%0A            DFS(res, s, start+1, rmL, rmR, open, sb.append(c));%0A        %7D%0A        sb.setLength(len);  //%E6%81%A2%E5%A4%8D%E5%8E%9F%E9%95%BF%E5%BA%A6%0A    %7D%0A%0A%0A%7D%0A

Remove Invalid Parentheses