亲宝软件园·资讯

展开

python有效的括号判断

修炼之路 人气:0

题目描述

给定一个只包括 '(',')','{','}','[',']'的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

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详解

总结

加载全部内容

相关教程
猜你喜欢
用户评论