Leetcode: Remove Invalid Parentheses

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

Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

 1 public class Solution {
 2     public List<String> removeInvalidParentheses(String s) {
 3         List<String> res = new ArrayList<String>();
 4         if (s==null || s.length()==0)  {
 5             res.add("");
 6             return res;
 7         }
 8         int diff=0, openN=0, closeN=0; 
 9         char[] arr = s.toCharArray();
10         for (int i=0; i<arr.length; i++) {
11             if (arr[i] == ‘(‘) diff++;
12             else if (arr[i] == ‘)‘) {
13                 if (diff == 0) closeN++;
14                 else diff--;
15             }
16         }
17         openN = diff;
18         diff = 0;
19         if (openN==0 && closeN==0) {
20             res.add(s);
21             return res;
22         }
23         
24         //backtracking
25         dfs(arr, res, 0, diff, openN, closeN, new StringBuffer());
26         return res;
27     }
28     
29     public void dfs(char[] arr, List<String> res, int cur, int diff, int openN, int closeN, StringBuffer sb) {
30         if (diff < 0) return;
31         if (cur == arr.length) {
32             if (openN==0 && closeN==0) {
33                 res.add(sb.toString());
34             }
35             return;
36         }
37         if (arr[cur]!=‘(‘ && arr[cur]!=‘)‘) {
38             sb.append(arr[cur]);
39             dfs(arr, res, cur+1, diff, openN, closeN, sb);
40             sb.deleteCharAt(sb.length()-1);
41         }
42         else if (arr[cur] == ‘(‘) {
43             //choice one: keep this ‘(‘ in stringbuffer, but in order to avoid duplicate, has to keep all consecutive ‘(‘
44             int i=1;
45             while (cur+i<arr.length && arr[cur+i]==‘(‘) i++;
46             sb.append(arr, cur, i);
47             dfs(arr, res, cur+i, diff+i, openN, closeN, sb);
48             sb.delete(sb.length()-i, sb.length());
49             
50             //choice two: remove this ‘(‘ in stringbuffer
51             if (openN > 0) {
52                 dfs(arr, res, cur+1, diff, openN-1, closeN, sb);
53             }
54         }
55         else if (arr[cur] == ‘)‘) {
56             //choice one: keep this ‘)‘ in stringbuffer, but in order to avoid duplicate, has to keep all consecutive ‘)‘
57             int i=1;
58             while (cur+i<arr.length && arr[cur+i]==‘)‘) i++;
59             sb.append(arr, cur, i);
60             dfs(arr, res, cur+i, diff-i, openN, closeN, sb);
61             sb.delete(sb.length()-i, sb.length());
62             
63             //choice two: remove this ‘)‘ in stringbuffer
64             if (closeN > 0) {
65                 dfs(arr, res, cur+1, diff, openN, closeN-1, sb);
66             }
67         }
68     }
69     
70 }