#20 Valid Parentheses——Top 100 Liked Questions

谁借莪１个温暖的怀抱￠ 2022-02-02 06:41 156阅读 0赞

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

An input string is valid if:

1.  Open brackets must be closed by the same type of brackets.
2.  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.
> 
> """