Easy, Short, Concise and Fast Java DFS 3 ms solution


  • 267

    For a better view see here

    Key Points:

    1. Generate unique answer once and only once, do not rely on Set.
    2. Do not need preprocess.
    3. Runtime 3 ms.

    Explanation:
    We all know how to check a string of parentheses is valid using a stack. Or even simpler use a counter.
    The counter will increase when it is ‘(‘ and decrease when it is ‘)’. Whenever the counter is negative, we have more ‘)’ than ‘(‘ in the prefix.

    To make the prefix valid, we need to remove a ‘)’. The problem is: which one? The answer is any one in the prefix. However, if we remove any one, we will generate duplicate results, for example: s = ()), we can remove s[1] or s[2] but the result is the same (). Thus, we restrict ourself to remove the first ) in a series of concecutive )s.

    After the removal, the prefix is then valid. We then call the function recursively to solve the rest of the string. However, we need to keep another information: the last removal position. If we do not have this position, we will generate duplicate by removing two ‘)’ in two steps only with a different order.
    For this, we keep tracking the last removal position and only remove ‘)’ after that.

    Now one may ask. What about ‘(‘? What if s = ‘(()(()’ in which we need remove ‘(‘?
    The answer is: do the same from right to left.
    However a cleverer idea is: reverse the string and reuse the code!
    Here is the final implement in Java.

    Java

    public List<String> removeInvalidParentheses(String s) {
        List<String> ans = new ArrayList<>();
        remove(s, ans, 0, 0, new char[]{'(', ')'});
        return ans;
    }
    
    public void remove(String s, List<String> ans, int last_i, int last_j,  char[] par) {
        for (int stack = 0, i = last_i; i < s.length(); ++i) {
            if (s.charAt(i) == par[0]) stack++;
            if (s.charAt(i) == par[1]) stack--;
            if (stack >= 0) continue;
            for (int j = last_j; j <= i; ++j)
                if (s.charAt(j) == par[1] && (j == last_j || s.charAt(j - 1) != par[1]))
                    remove(s.substring(0, j) + s.substring(j + 1, s.length()), ans, i, j, par);
            return;
        }
        String reversed = new StringBuilder(s).reverse().toString();
        if (par[0] == '(') // finished left to right
            remove(reversed, ans, 0, 0, new char[]{')', '('});
        else // finished right to left
            ans.add(reversed);
    }

  • 7

    This is absolutely awesome. I've just spent a lot of time on careful preprocessing and finally got a really complicated algorithm running in 7 ms, but I never thought about reversing the string!


  • 12
    P

    I spend some time to understand this algorithm. This is really an awesome one.

    This judgement I didn't understand at first.

    if (par[0] == '(') 
    

    This is used to check if the current 's' is reversed version, if it is not, that means still need to check the reversed string to make it legal, if it is reversed version 's', then you've checked both ordered and reverse ordered. What you have now is legal pattern.


  • 0

    You are right!
    I had some comment lines on this fact originally. Then somehow it is removed...


  • 7
    P

    I wrote a C++ version based on your algorithm, it runs 0ms ans beats 97.73% C++ codes.

       class Solution {
        private:
            vector<string> res;
            string p={'(',')'};
            void helper(string& s, int si, int sj, int rev){
                int stn=0;
                for(int i=si;i<s.size();i++){
                    if(s[i]==p[rev]) stn++;
                    else if(s[i]==p[1-rev]) stn--;
                    if(stn<0){
                        for(int j=sj;j<=i;j++){
                            if(s[j]==p[1-rev] && (j==sj || s[j-1]!=p[1-rev])){
                                string t=s.substr(0,j)+s.substr(j+1);
                                helper(t, i, j, rev);
                            }
                        }
                        return ;
                    }
                }
                string rs=s;
                reverse(rs.begin(), rs.end());
                if(p[rev]=='('){
                    helper(rs, 0, 0, 1-rev);
                }else{
                    res.push_back(rs);
                }
            }    
        public:
            vector<string> removeInvalidParentheses(string s) {
                res.clear();
                helper(s, 0, 0, 0);
                return res;
            }
        };
    

    About the last_i, last_j, I though it would be OK to passing just last_i as both search start of i and j, but it turns out not, the "legal prefix" here means "in order legal", that means within the prefix, number of '(' is equal or greater than number of ')', that means you can search j within previous legal prefix to make current prefix to i legal.

    An example is :
    '()))()))'


  • 1

    It sure would run in 0ms for C/C++. I have no doubt for that.

    Glad you understand it well~


  • 1
    B

    I think in the final part of remove() function, it slightly better to first check if stack == 0. If it's 0, then there's no need to run through the reversed string even if you haven't (saving a bit of time), just print the string (reverse if needed). If stack > 0, then check the reversed string.


  • 0
    B

    May I ask what is the complexity on this? Both time and space.

    Thanks in advance.


  • 0

    I am not so sure~I think If there are k unique answers then this algorithm runs in roughly O(nk), where n is the length of the string.


  • 0
    B

    Could you please give some more explanation? I totally have no idea how to analyze this.

    BTW, I saw you on 1point3acres.

    Haha ~


  • 4

    I am everywhere wahahaha~

    The program only generates valid answers. Every path in the search generates one valid answer. The whole search space is a tree with k leaves. The number of nodes in the tree is roughly O(k). But this is not always true, for example a degenerated tree.

    To generate one node it requires O(n) time from the string concatenation among other things. So roughly O(nk). Accurately O(nm) where m is the total "number of recursive calls" or "nodes in the search tree". Then you need to relate m to n in the worst case.

    I wouldn't worry too much about the accurate complexity analysis of this problem. It would require more mathematics than an interview cares.


  • 0
    B

    Thanks a lot!!!

    It's awesome to start from the result to analyse.


  • 0
    B

    Can I ask a favor? I found that you are really good at complexity analysis. Would you please take some time to answer the following question? That'll be really helpful !!!

    longest-palindromic-substring


  • 6
    P

    This solution is AWESOME! I spent some time to understand it and wrote a Python version. Best is 48ms. Thanks for sharing this!!!

    class Solution(object):
        def removeInvalidParentheses(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            result = []
            self.remove(s, result, 0, 0, ('(', ')'))
            return result
        
        def remove(self, s, result, last_i, last_j, par):
            count = 0
            for i in xrange(last_i, len(s)):
                count += (s[i] == par[0]) - (s[i] == par[1])
                if count >= 0:
                    continue
                for j in xrange(last_j, i + 1):
                    if s[j] == par[1] and (j == last_j or s[j - 1] != par[1]):
                        self.remove(s[:j] + s[j + 1:], result, i, j, par)
                return
            reversed_s = s[::-1]
            if par[0] == '(':
                self.remove(reversed_s, result, 0, 0, (')', '('))
            else:
                result.append(reversed_s)

  • 1
    C

    Can you explain more about the
    if(s[j]==p[1-rev] && (j==sj || s[j-1]!=p[1-rev]))?

    I don't quite understand it. Thanks


  • 0
    D

    OMG..Although the code is concise,it actually contains a lot of tricks.this is incredibly smart..


  • 0
    L

    Holy Gee! This solution is incredibly AWESOME!


  • 0
    K

    reverse string, the bulb in my head just lights up


  • 0
    A

    Awesome algorithm. But really hard to understand.

    For if(s[j]==p[1-rev] && (j==sj || s[j-1]!=p[1-rev])), I think it means that, when the prefix is not valid, it try to find the first p[1-rev] to delete. The first can either be s[sj] if s[sj] == p[1-rev], or can be latter ones, that dose not followed by a same sign.

    The part that most hardly for me to write, is the "return " in the middle.


  • 0

    so amazing!!!


Log in to reply
 

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