分类：String
考察知识点：String/Stack
最优解时间复杂度：O(n)
最优解空间复杂度：O(n)
20. Valid Parentheses
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
代码：
我的方法:
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
if s=="":
return True
elif len(s)==1:
return False
stack=[]
for ch in s:
if ch=="(":
stack.append(")")
elif ch=="[":
stack.append("]")
elif ch=="{":
stack.append("}")
else:
if len(stack)==0:
return False
elif stack.pop()!=ch:
return False
return len(stack)==0
讨论：
1.这道题是一道典型的类型题，这种题目还会经常在面试中出现，要用stack的方法去解
典型Stack题！加油！
