Simple Python solution with stack


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


  • 0
    A

    Similar idea. Looks clean.

    def isValid(self, s):
            """
            :type s: str
            :rtype: bool
            """
            d = {')': '(', '}': '{', ']': '['}
            stack = []
            for c in s:
                if c in d:
                    if not stack or stack.pop() != d[c]:
                        return False
                else:
                    stack.append(c)
            return not stack

  • 0
    R
    def isValid(self, s):
            stack = []
            dic = {'(': ')', '{':'}', '[':']'}
            for c in s:
                if c in dic:
                    stack.append(c)
                else:
                    if not stack or dic[stack.pop()] != c:
                        return False
            return not stack
    

Log in to reply
 

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