打卡群2刷题总结1005——有效的括号
leetcode第20题：有效的括号
https://leetcode-cn.com/problems/valid-parentheses/
【题目】
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
【思路】
使用栈结构，遍历字符串，遇到左括号，则压栈；遇到右括号，则弹栈（左括号），并判断两个括号是否对应。
注意：弹栈时，可能栈为空！
【代码】
python版本
class Solution:
def isValid(self, s: str) -> bool:
stack = []
d = {
')': '(',
']': '[',
'}': '{'
}
for i, si in enumerate(s):
# 遇到右括号，判断栈里是否有对应的左括号
if si in d.keys():
if len(stack) == 0 or stack[-1] != d[si]:
return False
else:
stack.pop()
# 遇到左括号，压栈
else:
stack.append(si)
return len(stack) == 0
【相似题目】
71. 简化路径
解题思路：按照/分割字符串后，遍历元素：遇到.则忽视；遇到..则弹栈；遇到其它元素则压栈。
84. 柱状图中最大的矩形
解题思路：遍历元素，如果元素比栈顶元素更大，则压栈，否则不断弹栈。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-10-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读