#20 Valid Parentheses——Top 100 Liked Questions-蒲公英云

#20 Valid Parentheses——Top 100 Liked Questions

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

“””

第一次：使用栈stack，如果遇到左括号，压入栈中，如果遇到右括号：1）如果stack为空，没有与左括号匹配的右括号，返回false；2）stack不为空，弹出左括号，判断是否与当前右括号匹配，如果匹配，匹遍历下一个括号，不匹配，返回false；3）遍历完成后，看stack中是否有多余的左括号没找到匹配对象，有则返回false

“””
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for bra in s:
            if bra in ['(', '[', '{']:
                stack.append(bra)
            else:
                if len(stack) == 0:
                    return False
                else:
                    check = stack.pop()
                    if (check == '(' and bra == ')') or (check == '[' and bra == ']') or (check == '{' and bra == '}'):
                        continue
                    else:
                        return False
        return len(stack) == 0
“””

Runtime: 20 ms, faster than 93.77% of Python online submissions for Valid Parentheses.

Memory Usage: 11.9 MB, less than 5.20% of Python online submissions for Valid Parentheses.

“””