Beats 100% of Python submissions + comments


  • 0
    A

    The key to this solution is that you must close the last open paren before any other open paren.

    class Solution(object):
        def isValid(self, s):
            """
            :type s: str
            :rtype: bool
            """
            valid = True
            
            # odd strings cannot be valid -- one paren too many open or closed
            if len(s) % 2 != 0:
                return not valid
            # store the opening and closing parens in variables for easy recall
            openers, closers = "({[", ")}]"
            # store the opposite paren for each paren
            opps = {"(":")", ")":"(", "{":"}", "}":"{", "[":"]", "]":"["}
            # keep track of all open parens
            currOpen = ""
            for c in s:
                if c in openers:
                    currOpen += c
                if c in closers:
                    if len(currOpen) == 0:
                        return not valid
                    # if c does not close the last paren opened -- not valid
                    if opps[c] != currOpen[-1]:
                        return not valid
                    else:
                        currOpen = currOpen[:-1]
    
    # shouldn't have unclosed parens left over
            if len(currOpen) != 0:
                return not valid
            return valid
    

Log in to reply
 

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