Java BFS(40ms) and DFS(17ms) without HashSet


  • 4
    C

    The critical step is to recognize that this question can be reformulated as below

    Given Array[], find all possible combinations which can form a valid parenthesis. And among all of them, find the longest. So first I'd recommend to work on question https://leetcode.com/problems/subsets-ii/

    So what we'll try to do is to generate unique combinations using either Iterative(BFS) or recursive(DFS). Two observations can help

    1. continuous (((+ or )))+ are guaranteed to be duplicate
    2. if if we define an extra element to identify the position of last removed index, then next BFS, we'll only need to start from there, instead of loop from 0 to str.length. According to combination C(n,k) = C(n-1,k-1) + C(n-1,k)

    BFS

    public List<String> removeInvalidParentheses(String s) {
        Queue<String> queue = new LinkedList<>();
        Queue<Integer> ends = new LinkedList<>(); //here consider ends is index of last removed element!
    
        List<String> res = new ArrayList<>();
        int size = 1;
        queue.offer(s);
        ends.add(s.length());
    
        while (!queue.isEmpty()) {
            String str = queue.poll();
            int end = ends.poll();
    
            if (isValid(str)) res.add(str);
    
            //only when not found, we need to consider next level
            if (res.size() > 0) continue;
            for (int i = end - 1; i >= 0; i--) {
                if (str.charAt(i) != '(' && str.charAt(i) != ')') continue;
                String next = (new StringBuilder()).append(str.substring(0, i)).append(str.substring(i + 1)).toString();
                queue.offer(next);
                ends.add(i);
                
                //skip continuous ')' and '('
                while (i > 0 && str.charAt(i) == str.charAt(i - 1)) i--;
            }
    
            //check level finish, if not found, go on to next level
            if (--size == 0) {
                if (res.size() > 0) break;
                size = queue.size();
            }
        }
    
        return res;
    }
    
    
    private boolean isValid(String s) {
        int open = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') open++;
            else if (c == ')') open--;
            if (open < 0) return false;
        }
        return open == 0;
    }
    

    DFS

    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();
        dfs(res, s, 0, new StringBuilder(), 0);
    
        return res;
    }
    
    
    private void dfs(List<String> res, String s, int start, StringBuilder path, int open) {
        if (open < 0) return;
        if (!res.isEmpty() && path.length() + s.length() - start < res.get(0).length()) return;
        if (start == s.length()) {
            if (open == 0 && (res.size() == 0 || path.length() == res.get(0).length())) res.add(path.toString());
            return;
        }
    
        path.append(s.charAt(start));
        if (s.charAt(start) != '(' && s.charAt(start) != ')') dfs(res, s, start + 1, path, open);
        else {
            dfs(res, s, start + 1, path, open + (s.charAt(start) == '(' ? 1 : -1));
            while (start < s.length() - 1 && s.charAt(start) == s.charAt(start + 1)) start++;
        }
    
        path.deleteCharAt(path.length() - 1);
        dfs(res, s, start + 1, path, open);
    }

  • 0
    Y

    Hi, both your solution and my solution are DFS. very similar. yet mine is 100+ ms. Wondering how you managed to find the max length?

    My code;

    =======

    public List<String> removeInvalidParentheses(String s) {
        // 7:41pm - 8:20pm
        // DFS solution:
        // scan left to right, time complexity O(n^3)
    	Set<String> result = new HashSet<String>(); 
    	//System.out.println("size:" + result.size());
        removeInvalidParenthesesHelper(s.toCharArray(), 0, 0, new StringBuilder(), result);
        Map<Integer, List<String>> resultByLength = new HashMap<Integer, List<String>>();
        int maxLen = 0;
        for (String ss : result) {
        	if (! resultByLength.containsKey(ss.length())) {
        		resultByLength.put(ss.length(), new ArrayList<String>());
        	}
        	resultByLength.get(ss.length()).add(ss);
        	if (ss.length() > maxLen) {
        		maxLen = ss.length();
        	}
        }
        return resultByLength.get(maxLen);
    }
    
    private void removeInvalidParenthesesHelper(char[] array, int numLeft, int curr, StringBuilder sb, Set<String> result) {
        // numLeft for opening left brackets that are unresolved
        if (curr == array.length) {
            if (numLeft == 0) {
                result.add(sb.toString());
            }
            return;
        }
        if (array[curr] == '(') {
            // skip it
            removeInvalidParenthesesHelper(array, numLeft, curr + 1, sb, result); 
            // take it
            sb.append(array[curr]);
            removeInvalidParenthesesHelper(array, numLeft + 1, curr + 1, sb, result);
            sb.deleteCharAt(sb.length()-1);
        } else if (array[curr] == ')') {
            if (numLeft > 0) {
                // take it
                sb.append(array[curr]);
                removeInvalidParenthesesHelper(array, numLeft - 1, curr + 1, sb, result);
                sb.deleteCharAt(sb.length()-1);                
            }
            // skip it
            removeInvalidParenthesesHelper(array, numLeft, curr + 1, sb, result);
        } else {
            // take it
            sb.append(array[curr]);
            removeInvalidParenthesesHelper(array, numLeft, curr + 1, sb, result);   
            sb.deleteCharAt(sb.length()-1); 
        }
    } 
    

  • 0
    C

    It's a bit hard to explain, but I'll try. Since you are checking the validity using criteria how many '(' is open. If you try to track the dfs, each call of the function will first check the longer variation, then the shorter variation. Basically you can interpret dfs as following - find one longest valid parentheses starting at some index i. (prove this by contradiction, given dfs(i) returns l1. suppose it's not the longest, and dfs(j<i) return l2>l1 -> contradiction with assumption, since i<j, dfs(i)==dfs(j)

    I think it would be clearer if you remove the HashMap in your code. Then track a short test case, you'll see the first variation dfs found is the longer one.


  • 0
    V

    continuous (((+ or )))+ are guaranteed to be duplicate

    I dont get this part yet, can you explain a litle bit?

    I think I got it, there no point to remove one then add the same thing back.


  • 0
    C

    another way to look at it is, duplicated are caused when you pick the same symbols in different order. Consider, e.g. ((( select 2 will be the same as (( select 2.


  • 2
    N

    What would be the time complexity for this solution ?


Log in to reply
 

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