Concise Python with Clear Explanations using Stack and Dict

  • 0

    We can simply create a dictionary to simplify our loop. At the same time, we use stack to check two things:

    • If anywhere in the string, there are more right elements than left elements (e.g. if we have seen 2 "}" but only 1 "{", we know that we failed already)
    • If we have closed something alien inside. "( [ ) ]", we can simply check if the last added element (using .pop()) is matching element of the current element (e.g. in our example, when we close with ")" it does not match "[" so we terminate.
    class Solution(object):
        def isValid(self, s):
            stack = []
            D = {")" : "(", "]" : "[", "}" : "{"}
            for char in s:
                if char in D.values():
                    if stack == [] or stack.pop() != D[char]:
                        return False
            return stack == []

Log in to reply

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