class Solution:
def isValid(self, s: str) -> bool:
if len(s)%2!=0:
return False
stack=[]
dic={
")":"(",
"]":"[",
"}":"{",
}
for i in s:
if i not in dic:
stack.append(i)
elif not stack or dic[i]!=stack.pop():
return False
if stack:
return False
else:
return True
思路:
- 使用栈,用python中的list实现栈结构
- 使用dic储存对应的符号
- 题解是:当有左括号时入栈,当遍历到右括号时,看这个右括号与栈顶的左括号是否匹配,如果匹配,就弹出,如果不匹配,就返回false
- 优化是:当这个stack根本就没有加进去括号时,返回false,这表示至少开头的元素没有左括号
更加优化
class Solution:
def isValid(self, s: str) -> bool:
dic = {
'{': '}', '[': ']', '(': ')', '?': '?'}
stack = ['?']
for c in s:
if c in dic: stack.append(c)
elif dic[stack.pop()] != c: return False
return len(stack) == 1
思路:
- 给这个stack先添加一个辅助元素,如果把
?
弹出了,没有与之匹配的括号,直接返回false(其实跟之前的如果栈为空直接返回false
是一样的)