Short Python BFS


  • 36

    Solution 1

    Being lazy and using eval for checking:

    def removeInvalidParentheses(self, s):
        level = {s}
        while True:
            valid = []
            for s in level:
                try:
                    eval('0,' + filter('()'.count, s).replace(')', '),'))
                    valid.append(s)
                except:
                    pass
            if valid:
                return valid
            level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}
    

    Update: Meh, ok, checking it myself isn't that much longer, and it's three times as fast:

    Solution 2

    def removeInvalidParentheses(self, s):
        def isvalid(s):
            ctr = 0
            for c in s:
                if c == '(':
                    ctr += 1
                elif c == ')':
                    ctr -= 1
                    if ctr < 0:
                        return False
            return ctr == 0
        level = {s}
        while True:
            valid = filter(isvalid, level)
            if valid:
                return valid
            level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}
    

    Solution 3

    Just a mix of the above two.

    def removeInvalidParentheses(self, s):
        def isvalid(s):
            try:
                eval('0,' + filter('()'.count, s).replace(')', '),'))
                return True
            except:
                pass
        level = {s}
        while True:
            valid = filter(isvalid, level)
            if valid:
                return valid
            level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}
    

    Solution 4

    Yet another way to do isvalid.

    def removeInvalidParentheses(self, s):
        def isvalid(s):
            s = filter('()'.count, s)
            while '()' in s:
                s = s.replace('()', '')
            return not s
        level = {s}
        while True:
            valid = filter(isvalid, level)
            if valid:
                return valid
            level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}

  • 2
    J

    You have never stopped to amaze me


  • 8

    The king of clean and amazing code


  • 0
    T

    @StefanPochmann amazing, so clean and pythonic


  • 3

    Meh, what a noob code, could've made Solution 2 shorter like this :-)

        def isvalid(s):
            ctr = 0
            for c in s:
                ctr += (c == '(') - (c == ')')
                if ctr < 0:
                    return False
            return ctr == 0
    

    Another way would be ctr += ('()'.find(c) + 2) % 3 - 1 but that's not just complicated but also longer and slower...

    I quite like filter('()'.count, s), though, and don't even remember having done that :-P


  • 11

    What if input is like 'a)b)c)d)e)f)g)h)i)j)k)l)m)n)o)p)(((((((((((((((((((('. BFS above will search too many useless states and get stuck.


  • 0
    A
    This post is deleted!

  • 0
    A

    Really Nice and clean code ! thank you for sharing


  • 0
    L

    AMAZING code!


  • 0

    I improve your solution 2 a little bit. Instead of check whether s is invalid, we can also count the # of unmatched parenthesizes, either left or right. Assume there are k such parenthesizes, we know that we need to remove k of them. In this case, the BFS can go straight to level k and thus a little bit faster.

    class Solution(object):
        def removeInvalidParentheses(self, s):
            
            def countInvalidParentheses(string):
                left_ctr = right_ctr = 0
                for c in string:
                    if c == '(':
                        left_ctr += 1
                    elif c == ')':
                        if left_ctr > 0:
                            left_ctr -= 1
                        else:
                            right_ctr += 1
                return left_ctr + right_ctr
            
            level = {s}
            for _ in range(countInvalidParentheses(s)):
                level = {s[:i] + s[i+1:] for s in level for i in range(len(s))}
                
            return filter(lambda string: countInvalidParentheses(string) > 0, level)
    

    I am surprised it can pass the auto grader. I agree with @Misaka-10032. This solution will be very slow when # of parentheses is large, e.g. )))))))))))))))))))))


  • 0
    J

    how do you analyze the time complexity of this code


  • 0
    A

    @StefanPochmann
    Is this the best we can achieve for this problem ?

    How do we calculate time complexity ? This is how I am interpreting it, when length of input string is N:

    Time complexity for isvalid function is n.

    For level 1, one string of length N, and hence N.
    For level 2, N strings with length N-1, and hence complexity N*(N-1)
    For level 3, N*(N-1) strings with each length N-2, and hence time complexity N*(N-1)*N(N-2) and so on.

    Does that mean complexity is O(N^N) ?


Log in to reply
 

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