Python solution with Stack implementation


  • 0
    E
    class Stack():
        def __init__(self):
            self.items = []
        def push(self, item):
            self.items.append(item)
            
        def pop(self):
            return self.items.pop()
        def size(self):
            return len(self.items)
        def isEmpty(self):
            return self.items == []
    
    def matches(open, close):
        opens = "{(["
        closes = "})]"
        return opens.index(open) == closes.index(close)
    
    class Solution(object):
        def isValid(self, s):
            """
            :type s: str
            :rtype: bool
            """
            index = 0
            balanced = True
            st = Stack()
            while index < len(s) and balanced:
                symbol = s[index]
                if symbol in "{([":
                    st.push(symbol)
                else:
                    if st.isEmpty():
                        balanced = False
                    else:
                        top = st.pop()
                        if not matches(top, symbol):
                            balanced = False
                        else:
                            balanced = True
                index += 1
            if st.isEmpty() and balanced == True:
                return True
            else:
                return False
    

  • 0

    Could be shorter.
    You implemented a stack but it is not efficient than a list. You just wrap append and pop operations in it.

    class Solution(object):
        def isValid(self, s):
            """
            :type s: str
            :rtype: bool
            """
            stack = []
            for c in s:
                stack.append(c)
                if len(stack) > 1 and "".join(stack[-2:]) in ["()", "[]", "{}"]:
                    stack.pop()
                    stack.pop()
            return not stack
    

Log in to reply
 

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