给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
- show the code1:
class Solution:
def isValid(self, s: str) -> bool:
while '()' in s or '[]' in s or '{}' in s:
s = s.replace('()','')
s = s.replace('[]','')
s = s.replace('{}','')
return s==''
- show the code2:
class Solution:
def isValid(self, s: str) -> bool:
if not s:
return True
if s[0]==']' or s[0]==')' or s[0]=='}':
return False
res = []
for i in s:
if i == '[' or i == '(' or i == '{':
res.append(i)
elif res and res[-1] == '[' and i == ']':
res.pop()
elif res and res[-1] == '(' and i == ')':
res.pop()
elif res and res[-1] == '{' and i == '}':
res.pop()
else:
return False
return not res
- show the code3:
class Solution:
def isValid(self, s: str) -> bool:
res,dic = [],{']':'[',')':'(','}':'{'}
for i in s:
if i in dic:
ii = res.pop() if res else 'error'
if ii != dic[i]:
return False
else:
res.append(i)
return not res
- 上面三种方法中，法一算是比较bug的方法，用python还是很简单的，直接使用replace函数就好了。
- 第二三中方法是一样的思路，利用栈的先进后出来做，按照题目的要求，我们知道开括号闭括号必须顺序合格，这意味着开括号后面必须接闭括号，而且要是同一类型的
- code2稍微繁琐了一些，相当于考虑到了所有情况，比如空字符串有效，以闭括号开头的字符串无效。
- code3则是code2的改进，我们可以考虑利用一个字典来存储闭括号和其对应的开括号，这样就不用像code2那样枚举所有的情况了，代码简单化了很多，这里 充分体现了耗费一定的空间来存储变量的好处，特别是像字典（哈希表）这样的数据结构。
