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 

 

思路

---

　　我们可以设置一个辅助空间栈来保存括弧的左半边，然后进行遍历。当遍历到不是右半边括弧时，我们就弹出最上面的括弧来和当前括弧进行对比，查看是否是有效括弧。 时间复杂度为O(n)(n为字符串的长度), 空间复杂度为O(n)。

 

图示思路

---

    

    

 

 

      一直到遍历完毕

 

代码

---

 

 1 class Solution(object):
 2     def isValid(self, s):
 3         """
 4         :type s: str
 5         :rtype: bool
 6         """
 7         if len(s) < 1:             # 空字符串直接返回
 8             return True
 9         tem_dict = {')':'(', '}':'{', ']':'['}        # 设置辅助字典
10         stack = []                                  # 设置辅助栈
11         for i in s:                             # 进行遍历
12             if i not in tem_dict:
13                 stack.append(i)                 
14             else:
15                 if stack:                     # 右括弧进行选择
16                     t = stack.pop()
17                     if t != tem_dict[i]:
18                         return False
19                 else:
20                     return False
21         if stack:                           # 栈不为空的话返回False
22             return False
23         return True
24