有效的括号
题目
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
解法一
思路
后遇到的左括号总是先匹配右括号,先遇到的左括号总是后匹配右括号,符合栈先进后出的原理。
dic = {')': '(','}': '{',']': '['}
遍历字符串s,如果i是左括号加到栈顶,
如果i是右括号,判断d里面有没有,如果有我们要出栈,但是这里可能会有栈空的情况要注意判断,那出栈就出错了,
所以如果在dic里面,栈不是空的,且栈顶的元素与i相等,
如果不满足这两个条件直接返回False
如果满足就出栈,最后栈应该是空的
解法
class Solution:
def isValid(self, s: str) -> bool:
if len(s) % 2 == 1:
return False
dic = {')': '(','}': '{',']': '['}
stack = []
for i in s:
# 如果i是右括号
if i in dic:
if not stack or dic[i] != stack[-1]:
return False
stack.pop()
# 如果i是左括号
else:
stack.append(i)
return not stack
时间复杂度:O(n)
执行用时:32 ms
内存消耗:15.1 MB
解法二
思路
dic = {'{': '}', '[': ']', '(': ')', '?': '?'}
上面提到了空栈出栈的问题,索性这里直接定义一个长度为一的栈stack = ['?']
遍历字符串s,如果i是左括号也就是在dic里面,入栈
如果i是右括号,dic[出栈的元素]不等于i,直接返回False
最后stack的长度还是1,说明进栈的元素全都出栈了,s是有效的括号
解法
class Solution:
def isValid(self, s: str) -> bool:
if len(s) % 2 == 1:
return False
dic = {'{': '}', '[': ']', '(': ')', '?': '?'}
stack = ['?']
for i in s:
# 如果i是左括号
if i in dic:stack.append(i)
# 如果i是右括号
elif dic[stack.pop()] != i:return False
return len(stack) == 1
时间复杂度:O(n)
执行用时:32 ms
内存消耗:15 MB