Java DFS solution, use one optimization


  • 1
    P

    First calculate the minimum number of steps to get the answer. The method fellows https://leetcode.com/discuss/68327/java-dfs-solution-with-optimizations.

    Then enumerate all the possible states and save the results. Pay attention, we should remove the duplicate results.

    public class Solution {
        List<String> res = new ArrayList<>();
        Set<String> hash = new HashSet<>();
        Stack<Character> stack = new Stack<>();
        int n, ans;
        public void search(String s, int p, String s1, int sum) {
            if (sum > ans)
                return;
            if (n == p) {
                if (stack.size() == 0)
                    hash.add(s1);
                return;
            }
            char c = s.charAt(p);
            if (c != '(' && c != ')')
                search(s, p+1, s1+c, sum);
            else {
                char d = '0';
                if (stack.isEmpty())
                    stack.push(c);
                else {
                    if (c == stack.peek() || c == '(')
                        stack.push(c);
                    else d = stack.pop();
                }
                search(s, p+1, s1+c, sum);
                if (d != '0')
                    stack.push(d);
                else stack.pop();
                search(s, p+1, s1, sum+1);
            }
        }
        public List<String> removeInvalidParentheses(String s) {
            this.n = s.length();
            ans = 0;
            int leftCnt = 0;
            for(int i = 0; i < n; i++) {
                if(leftCnt>0 && s.charAt(i)==')') {
                    ans--;
                    leftCnt--;
                }
                else if(s.charAt(i)==')')
                    ans++;
                else if(s.charAt(i)=='(') {
                    ans++;
                    leftCnt++;
                }  
            }
            search(s, 0, "", 0);
            res.addAll(hash);
            return res;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.