05_有效的括号

# ❌ "()[]{}" 是非对称的
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        # 解题思路：必须是偶数 中间切分 一边从左遍历 一边从右遍历 是相对应的
        """
        if not s:
            return True

        if len(s) % 2 != 0:
            return False

        length = len(s) // 2
        right = -1
        for i in range(length):
            if s[i]+s[right] not in ['()', '{}', '[]']:
                return False
            right -= 1

        return True


class Solution2(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        有点堆栈的意思 最中间肯定是() 或 [] 或 {}
        """
        a = {']': '[', ')': '(', '}': '{'}
        list1 = [0]
        for i in s:
            if i in a and list1[-1] == a[i]:
                list1.pop()
            else:
                list1.append(i)
        return len(list1) == 1


# leetcode 最优解 和上面的解法异曲同工
class Solution3(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        bracket = ("()", "[]", "{}")
        for i in s:
            if not stack:  # 为空时
                stack.append(i)
            else: # 不为空时
                if stack[-1]+i in bracket:
                    stack.pop()
                else:
                    stack.append(i)
        return stack == []