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. 柱状图中最大的矩形
解题思路:遍历元素,如果元素比栈顶元素更大,则压栈,否则不断弹栈。