leetcode | 20.有效的括号

20.有效的括号

题目描述

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

题目链接

思路

遍历字符串，遇到右括号将右括号入栈，遇到左括号判断此左括号是否与栈顶括号相同，若相同则将栈顶元素出栈，…，最后在遍历结束后判断栈是否为空，若为空则为有效括号。

代码

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s) % 2 == 1:
            return False

        stack = []
        for ch in s:
            if ch == '(' or ch == '[' or ch == '{':
                stack.append(ch)
            elif ch == ')' and len(stack) != 0:
                    if stack[-1] == '(':
                        stack.pop()
                    else:
                        return False
            elif ch == ']' and len(stack) != 0:
                    if stack[-1] == '[':
                        stack.pop()
                    else:
                        return False
            elif ch == '}' and len(stack) != 0:
                    if stack[-1] == '{':
                        stack.pop()
                    else:
                        return False
            else:
                return False

        if len(stack) == 0:
            return True
        else:
            return False

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

        pairs = {
            ")": "(",
            "]": "[",
            "}": "{"
        }
        stack = list()
        for ch in s:
            if ch in pairs:
                if not stack or stack[-1] != pairs[ch]:
                    return False
                stack.pop()
            else:
                stack.append(ch)

        return not stack




if __name__ == "__main__":
    slt = Solution()
    # s = "()"
    # s = "()[]{}"
    # s = "(]"
    # s = "([)]"
    # s = "{[]}"
    s = "]"
    ret = slt.isValid1(s)
    print(ret)