Simple Python solution with stack


  • 52
    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.


  • 3
    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

  • 6
    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?


  • 0
    S

    @Seasean said in Simple Python solution with stack:

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

    You can add a simple check for odd length at the top to catch them early and return False.

    def isValid(self, s):
      if len(s) % 2 == 1:
        return False
      ...
    

  • 0
    L

    @xiaoying10101 It is wrong when you have a single input '[' or'{' or'('


  • 0
    J

    Came up with similar solution. Nicely done!

    def isValid(self, s):
            stack = []
            for c in s:
                if c in ['(', '[', '{']:
                    stack.append(c)
                elif [] == stack or stack.pop() != {')':'(', ']':'[', '}':'{'}[c]:
                    return False
            return [] == stack
    

  • 0
    C

    @xiaoying10101

    I think your code can not deal with the situation when we input "[[".. I think judge whether the input is true is easier.


  • 0
    D

    @jimmydada said in Simple Python solution with stack:

    very good idea using empty stack

    what does that mean? one can return it rather than True?


Log in to reply
 

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