Q20 Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

解题思路：

模拟栈的操作，如果是(、[、}，则入栈；如果是 )、]、}，则出栈。如果匹配正确，最后栈为空，说明字符串有效。

Python实现：

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s) == 0:
            return False
        if s[0] != '(' and s[0] != '[' and s[0] != '{':
            return False
        stack = []  # 模拟栈的操作
        for i in range(len(s)):
            if s[i] == '(' or s[i] == '[' or s[i] == '{':
                stack.append(s[i])
            else:
                if len(stack) == 0:  # 栈中没有匹配 (、[、{ 的字符
                    return False
                ch = stack.pop()
                if ch == '(' and s[i] != ')' or ch == '[' and s[i] != ']' or ch == '{' and s[i] != '}':
                    return False
        if len(stack) == 0:
            return True
        else:
            return False

a = '[])'
b = Solution()
print(b.isValid(a))  # false