有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。示例 1:
输入: "()"
输出: true
方法一：利用列表实现栈
一开始想到的是大学《数据结构》里学过的栈的应用——括号匹配，不过当时写的是伪代码，要使用Python写还是搜了一阵子。
方法应该也是属于暴力法，如果是左括号就进栈，如果是右括号就与栈顶元素比较，看是否匹配。
最后判断栈是否为空，若为空，则匹配成功，否则匹配失败。
Python3版本如下：
class Solution:
def isValid(self, s: str) -> bool:
list = []
for i in range(len(s)):
if s[i] == '(' or s[i] == '[' or s[i] == '{':
list.append(s[i])
else:
if len(list) == 0:
return False
p = list.pop()
if (s[i] == ')' and p == '(') or (s[i] == ']' and p == '[') or (s[i] == '{' and p == '}'):
continue
else:
return False
if len(list) > 0 :
return False
return True
不过由于使用了栈，所以空间占用率比较大。
方法二：利用字典
看了题解给出的答案，可以提前把正确的配对放进字典内，这样相比方法一就省去了入栈的时间。
这里stack=['?']是为了避免字符串为类似‘]’这种只有右括号的情况，这种情况下由于没有左括号，stack.pop()会由于stack为空而出错。
而令stack=['?']之后，在最后判断栈是否为空时就不能用len(stack) == 0'了，因为我们stack里始终有一个?
class Solution:
def isValid(self, s: str) -> bool:
dic = {'{': '}', '[': ']', '(': ')', '?': '?'}
stack = ['?']
for c in s:
# 如果c是左括号，则入栈
if c in dic:
stack.append(c)
# 如果c是右括号，则将栈顶元素在字典中的值与c作比较
# 如果不等，则表示不匹配
elif dic[stack.pop()] != c:
return False
return len(stack) == 1
同样由于使用了栈，所以是空间换时间的做法，内存消耗比较大
