有效的括号
给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
样例
输入: "()"
输出: true
输入: "()[]{}"
输出: true
输入: "([)]"
输出: false
算法1
(栈+哈希表) $O(n)$
一.思路
1.核心思想:有效括号的,部分子表达式仍然是有效括号–>恰为栈格式:把最小括号对出栈+判空为真
2.优化:哈希表寻找括号
二.实现
遍历括号序列s
1.若栈中已有值:
1)找出在哈希表中的映射(对应括号);弹出
2)否则:此括号序列无效
2.若栈中无值:入栈
3.返回not stack (bool)
时间复杂度
参考文献
python 代码
class Solution:
def isValid(self, s: str) -> bool:
#难点1.python哈希表存储方式
#为什么要反着写;因为栈顶弹出+映射吗?
dic={')':'(', ']':'[', '}':'{'}
stack=[]
for i in s:
if stack and i in dic:
#i在栈中 且 i映射也在
if stack[-1]==dic[i]:
stack.pop()
else:
return False
else:
stack.append(i)
#难点2.有效时,栈空,真(bool)
return not stack