Easiest 9ms Java Solution


  • 123

    Here I share my DFS or backtracking solution. It's 10X faster than optimized BFS.

    1. Limit max removal rmL and rmR for backtracking boundary. Otherwise it will exhaust all possible valid substrings, not shortest ones.
    2. Scan from left to right, avoiding invalid strs (on the fly) by checking num of open parens.
    3. If it's '(', either use it, or remove it.
    4. If it's '(', either use it, or remove it.
    5. Otherwise just append it.
    6. Lastly set StringBuilder to the last decision point.

    In each step, make sure:

    1. i does not exceed s.length().
    2. Max removal rmL rmR and num of open parens are non negative.
    3. De-duplicate by adding to a HashSet.

    Compared to 106 ms BFS (Queue & Set), it's faster and easier. Hope it helps! Thanks.

    public List<String> removeInvalidParentheses(String s) {
        int rmL = 0, rmR = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                rmL++;
            } else if (s.charAt(i) == ')') {
                if (rmL != 0) {
                    rmL--;
                } else {
                    rmR++;
                }
            }
        }
        Set<String> res = new HashSet<>();
        dfs(s, 0, res, new StringBuilder(), rmL, rmR, 0);
        return new ArrayList<String>(res);
    }
    
    public void dfs(String s, int i, Set<String> res, StringBuilder sb, int rmL, int rmR, int open) {
        if (rmL < 0 || rmR < 0 || open < 0) {
            return;
        }
        if (i == s.length()) {
            if (rmL == 0 && rmR == 0 && open == 0) {
                res.add(sb.toString());
            }        
            return;
        }
    
        char c = s.charAt(i); 
        int len = sb.length();
    
        if (c == '(') {
            dfs(s, i + 1, res, sb, rmL - 1, rmR, open);		    // not use (
        	dfs(s, i + 1, res, sb.append(c), rmL, rmR, open + 1);       // use (
    
        } else if (c == ')') {
            dfs(s, i + 1, res, sb, rmL, rmR - 1, open);	            // not use  )
        	dfs(s, i + 1, res, sb.append(c), rmL, rmR, open - 1);  	    // use )
    
        } else {
            dfs(s, i + 1, res, sb.append(c), rmL, rmR, open);	
        }
    
        sb.setLength(len);        
    }

  • 2
    R

    Hello, actually, I read your code and think it is really cool to understand. I think all of things that I could know what the meaning is, but for sb.setLength(sb.length() - 1), I still do not know the meaning of that. Could you explain in detail? Thank you so much.


  • 13

    Hi @ruihuang, thanks for your question! To understand it, first make sure you understand the idea of backtracking which is extremely powerful. It's like going into a maze, and do a silly exhausted depth first search. When you meet the dead end, you need to go back to the last successful decision point, and try another direction.

    Back to this question. Based on 3 cases of current char: (, ) or others, we have 3 directions of at each maze point. Notice that no matter which direction we choose, there is exactly one char added. So after going to the dead end and gathering some chars, it will go backwards by removing one char at a time. (To make it clearer, I've modified the last line)

    So this is what I found extremely useful pattern but some might not know:

    int len = sb.length();
    ... backtracking ...
    sb.setLength(len);
    

    It has at least two merits:
    (1) StringBuilder is much more efficient than String concat.
    (2) sb.setLength(len) method is naturally adapted to backtracking.

    Hope it helps. Thanks!


  • 1
    R

    Great! Thanks a lot! I got it!


  • 1
    W

    Hi, I met a question

    When I tried to replace your

     int len = sb.length();
    -----------------------
        sb.setLength(len);
    

    part with

      StringBuffer temp = new StringBuffer(sb);
    ----------------------
    sb = temp;
    

    it turns out to be wrong.
    I just don't understand why it can not work this way
    Appreciate a lot if you can help me with the confusion.


  • 1
    Y

    Thanks for the elegant solution! superstar!!


  • 3

    @wopani007 to make it works, you cannot not miss any new StringBuilder around new DFS call. However, the run time decrease to 16ms because of unnecessary new instances of StringBuilder.

    This is an accepted version based on your method:

    public void DFS(Set<String> res, String s, int i, int rmL, int rmR, int open, StringBuilder sb) {
        if(i == s.length() && rmL == 0 && rmR == 0 && open == 0) {
            res.add(sb.toString());
            return;
        }
        if(i == s.length() || rmL < 0 || rmR < 0 || open < 0) {
            return;
        }
    
        char c = s.charAt(i);
        StringBuilder tmp = null;
    
        if(c == '(') {
            tmp = new StringBuilder(sb); 
            DFS(res, s, i + 1, rmL - 1, rmR, open, sb); 
            sb = tmp;
    
            tmp = new StringBuilder(sb);
            DFS(res, s, i + 1, rmL, rmR, open + 1, sb.append(c)); 
            sb = tmp;
    
        } else if(c == ')') {
            tmp = new StringBuilder(sb); 
            DFS(res, s, i + 1, rmL, rmR - 1, open, sb); 
            sb = tmp;
    
            tmp = new StringBuilder(sb); 
            DFS(res, s, i + 1, rmL, rmR, open - 1, sb.append(c)); 
            sb = tmp;
    
        } else {
            tmp = new StringBuilder(sb); 
            DFS(res, s, i + 1, rmL, rmR, open, sb.append(c));  
            sb = tmp;
        }
    }
    

    As you can see, we can instead use just one single StringBuilder, which makes code shorter and faster.


  • 0
    W

    Thanks for your reply, so the wrong result is due to the time limit? that makes sense


  • 0

    @wopani007, no I'm afraid it's not because of time limit.

    It's because each condition, (, ) or others, has 2 or 1 DFS, but you cannot just init 1 StringBuilder at the front, otherwise it will pick up a previous non-cleaned StringBuilder to append to a longer result.

    One setLength(len) works only because, in each condition (, ) or `others, there is only 1 char added.


  • 0
    N

    What would be the time and space complexity for this solution ?


  • 0
    Y

    The backtracking trick for StringBuilder is awesome!


  • 0
    Y

    I think it would be O(2^n) with n the length of the input string. Since each time we need to make a choice of adding the parentheses or not.


  • 0
    M

    Excellent solution! Thank you!


  • 1

    Thanks guys! The run time is fast because we have pruning for backtracking.


  • 3

    Set is not necessary if you don't generate duplicate strings in the first place.

    Check it out here


  • 0

    @dietpepsi, That's right. Your version is smart :)


  • 1
    L

    Why the time complexity isn't O(n*2^n)?Since there are O(2^n) substring we will generate and each substring we will take O(n) time to process. Correct me if I am wrong. Thanks.


  • 0
    L

    HashSet is disorder, why can you convert it to ArrayList?


  • 0
    G

    What is the time complexity for this solution?


  • 2
    A

    This is an awesome solution!

    The only thing that confuse me, is that what does the argument 'open' mean? My guessing is that it indicates how many left and right parentheses we removed, but I am not sure if it's right :(


Log in to reply
 

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