Simple Python solution with stack


  • 47
    X
    class Solution:
        # @return a boolean
        def isValid(self, s):
            stack = []
            dict = {"]":"[", "}":"{", ")":"("}
            for char in s:
                if char in dict.values():
                    stack.append(char)
                elif char in dict.keys():
                    if stack == [] or dict[char] != stack.pop():
                        return False
                else:
                    return False
            return stack == []
    

    It's quite obvious.


  • 0
    J

    Very good answer !!!
    I was thinking where does it return True~~very good idea using empty stack


  • 3
    F

    Very nice!

    else:
           return False
    

    is not necessary for the testing condition.


  • 2
    T

    Hi, here is shorter version. Checking if the char is in dict.values() is not necessary.

    def isValid(self, s):
        map = {')':'(', '}':'{', ']':'['}
        st = []
        for e in s:
            if st and (e in map and st[-1] == map[e]):
                st.pop()
            else:
                st.append(e)
        return not st

  • 5
    C

    here is my tricks of pop empty stack error

    class Solution(object):
        def isValid(self, s):
            """
            :type s: str
            :rtype: bool
            """
            stack = ['N']
            m = {')':'(',']':'[','}':'{'}
            for i in s:
                if i in m.keys():
                    if stack.pop() != m[i]:
                        return False
                else:
                    stack.append(i)
                    
            return len(stack) == 1

  • 0

    if i in m.keys() could write as if i in m :-)


  • 1
    T

    Isn't this bad since the for-loop won't terminate immediately when parentheses are invalid, such as encountering ']' after '('.

    Even worse, what if the first parenthesis is ']' and your script runs until it checks everything.


  • 0
    T

    You are correct. It is not optimized for early termination.


  • 1
    Q
    def isValid(self, s):
        left, right = set(['(','[','{']), dict([(')','('), (']','['),('}','{')])
        stack = []
        for v in s:
            if v in left:
                stack.append(v)
            elif not stack or right[v]!=stack.pop():
                return False
        return not stack

  • 0
    K
    class Solution(object):
        def isValid(self, s):
            stack = []
            dict = {'{': '}', '[': ']', '(': ')'}
            for char in s:
                if char in dict.keys():
                    stack.append(dict[char])
                elif stack==[] or stack.pop() != char:
                    return False
            return not stack

  • 0
    S

    Maybe I was wrong, but I am a bit confused what if the total number of char is odd, will the method work?


Log in to reply
 

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