python有效的括号判断
修炼之路 人气:0题目描述
给定一个只包括 '(',')','{','}','[',']'的字符串 s ,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
LeetCode原题地址:https://leetcode-cn.com/problems/valid-parentheses/
测试用例
示例 1
输入:s = “()”
输出:true
示例 2
输入:s = “()[]{}”
输出:true
示例 3
输入:s = “(]”
输出:false
示例 4
输入:s = “([)]”
输出:false
示例 5
输入:s = “{[]}”
输出:true
代码实现
实现这个算法我们可以利用栈的先进后出的特性,对于每个括号它需要找到与它匹配的括号。
我们先遍历字符串,将字符串的字符存入到栈中,当匹配到结束的括号时,如果此时栈不为空并且栈顶的字符与当前的括号相匹配时,我们将栈顶的字符进行出栈操作,否则直接返回False。如果最终栈为空表示每个括号都找到了匹配的结束括号,否则匹配失败。
class Solution: def isValid(self, s: str) -> bool: #如果字符串是奇数一定不满足条件 if len(s) % 2 != 0: return False #定义一个括号字典 bracket_dict = {")":"(","]":"[","}":"{"} #定义一个栈 stack = [] for c in s: #当匹配到括号的结束符时 if c in bracket_dict: #栈不能为空,并且栈顶要与结束的括号匹配 if len(stack) > 0 and bracket_dict[c] == stack[-1]: stack.pop() else: return False else: stack.append(c) return not stack s = Solution() print(s.isValid("()[]{}")) print(s.isValid("([)]"))
参考:LeetCode详解
总结
加载全部内容