个人中心
gpt4 book ai didi

每日一题：有效括号

转载 作者：撒哈拉 更新时间：2024-04-08 00:39:30 61 4
gpt4 key购买 nike

面对这个括号匹配的问题，我开始也有点迷茫，隐约觉得可以用栈（Stack）来解决。一起先来看看原题吧:


Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
 

Example 1:

Input: s = "()"
Output: true
Example 2:

Input: s = "()[]{}"
Output: true
Example 3:

Input: s = "(]"
Output: false
 

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

当成一个数学问题来看，先找出规则规律，如果先来一个关闭类型的括号（如），], })，那么直接就算false了，如果开和闭合没有成对出现，也会是false。我们可以拿一个Stack来保存open bracket,当循环的当前的字符是open bracket就push到stack。 当当前的字符是closed bracket则弹出顶部Stack的元素，看是否是对应的open bracket，如果是就继续循环，如果不是则返回false。 还要考虑一些边界情况，如果在弹出元素的时候刚好stack为空了，也说明没有配套的open bracket了，也应该返回false.

用Python实现的代码如下，非常清晰:


class Solution:
    def isValid(self, s: str) -> bool:
        bracketMap = {
            "(": ")",
            "{": "}",
            "[": "]"
        }

        stack = []

        for char in s:
            if char in bracketMap:
                # push the open bracket into the stack
                stack.append(char)
            else:
                # If the stack is empty or do not have the matching open bracket, it means the closed bracket does not have the related open bracket
                if len(stack) == 0 or bracketMap[stack.pop()] != char:
                    return False

        return len(stack) == 0

最后此篇关于每日一题：有效括号的文章就讲到这里了,如果你想了解更多关于每日一题：有效括号的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

61 4 0
文章推荐： 驾驭数据的能力，如同使用ChatGPT一样，是现代职场人的必修课
文章推荐： 从零开始学SpringBoot系列-SpringApplication
文章推荐： hive窗口分析函数使用详解系列一
文章推荐： 轻松上手Jackjson（珍藏版）
撒哈拉
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com