LeetCode link

first thought

  • have no idea…
  • it can be also solved by dfs, but I think bfs cost less, so just use bfs.
  • Have seen the answer. Because the problem is to delete minimum count of chars, so the root is the whole string, the neighbors is all the strings that deleted by one char.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    public List<String> removeInvalidParentheses(String s) {
        if (s == null) {
            return new ArrayList<>();
        }
        if (s.length() < 1) {
            List<String> empty = new ArrayList<>();
            empty.add("");
            return empty;
        }
        Set<String> visited = new HashSet<>();
        List<String> result = new ArrayList<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(s);
        boolean hasValid = false;
        while (!queue.isEmpty()) {
            String str = queue.poll();
            if (this.isValid(str)) {
                result.add(str);
                hasValid = true;
            } else if (!hasValid) {
                for (int i = 0; i < str.length(); i++) {
                    String sub1 = str.substring(0, i);
                    String sub2 = str.substring(i + 1, str.length());
                    String newStr = sub1.concat(sub2);
                    if (!visited.contains(newStr)) {
                        queue.add(newStr);
                        visited.add(newStr);
                    }
                }
            }
        }
        return result;
    }
    private boolean isValid(String s) {
        char[] chars = s.toCharArray();
        int count = 0;
        for (char c: chars) {
            if (c == '(') {
                count++;
            } else if (c == ')') {
                if (count == 0) {
                    return false;
                } else {
                    count--;
                }
            }
        }
        return count == 0;
    }
}

problem

wrong answer, there’s a empty string in the result.

Input:
“x(“
Output:
[“x”,””]
Expected:
[“x”]

reason

although have checked hasValid, but it still can be some smaller strings were added into the queue. (e.g first string is not valid, it’s children are added, the second string is valid, the rest substring will not be added. But the substring of the first one has already be added, so there would be some shorter but valid results.

modification

avoid the shorter cases.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
    public List<String> removeInvalidParentheses(String s) {
        if (s == null) {
            return new ArrayList<>();
        }
        if (s.length() < 1) {
            List<String> empty = new ArrayList<>();
            empty.add("");
            return empty;
        }
        Set<String> visited = new HashSet<>();
        List<String> result = new ArrayList<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(s);
        boolean hasValid = false;
        while (!queue.isEmpty()) {
            Queue<String> queue2 = new LinkedList<>();
            while (!queue.isEmpty()) {
                String str = queue.poll();
                if (this.isValid(str)) {
                    result.add(str);
                    hasValid = true;
                    queue2.clear();
                } else if (!hasValid) {
                    for (int i = 0; i < str.length(); i++) {
                        String sub1 = str.substring(0, i);
                        String sub2 = str.substring(i + 1, str.length());
                        String newStr = sub1.concat(sub2);
                        if (!visited.contains(newStr)) {
                            queue2.add(newStr);
                            visited.add(newStr);
                        }
                    }
                }
            }
            queue = queue2;
        }
        return result;
    }
    private boolean isValid(String s) {
        char[] chars = s.toCharArray();
        int count = 0;
        for (char c: chars) {
            if (c == '(') {
                count++;
            } else if (c == ')') {
                if (count == 0) {
                    return false;
                } else {
                    count--;
                }
            }
        }
        return count == 0;
    }
}