【LeetCode每天一题】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

思路

　　我们可以设置一个辅助空间栈来保存括弧的左半边，然后进行遍历。当遍历到不是右半边括弧时，我们就弹出最上面的括弧来和当前括弧进行对比，查看是否是有效括弧。时间复杂度为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