LeetCode解题之Valid Parentheses

原题

推断一个仅仅包括各种括号符号的字符串中括号的匹配情况。

注意点：

• 字符串中仅仅会包括”(“,”)”,”[“,”]”,”{“,”}”这些字符
• 括号匹配要注意顺序，字符串”([)]”是错误的匹配

样例：

输入: s=”(){}”
输出: True

输入: s=”(){}[”
输出: False

解题思路

典型的用栈来解决的问题，遇到左括号就压栈。遇到右括号时假设栈为空（相似”]]]”的情况）。则失败，否则取栈顶元素。看两个括号是否匹配。假设最后栈不为空（相似”[[[“的情况），则匹配失败。

AC源代码

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        # Valid str must be even
        if len(s) % 2 == 1:
            return False
        stack = []
        left = ("(", "[", "{")
        right = (")", "]", "}")
        zip(left,right)
        for v in s:
            if v in left:
                stack.append(v)
            else:
                if not stack:
                    return False
                p = stack.pop()
                if left.index(p) != right.index(v):
                    return False
        return len(stack) == 0


if __name__ == "__main__":
    assert Solution().isValid("({}){}") == True
    assert Solution().isValid("({)}") == False
    assert Solution().isValid("}}}") == False
    assert Solution().isValid("(((") == False

欢迎查看我的Github (https://github.com/gavinfish/LeetCode-Python) 来获得相关源代码。