[Leetcode] 0020. 有效的括号

这篇具有很好参考价值的文章主要介绍了[Leetcode] 0020. 有效的括号。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

20. 有效的括号

点击上方,跳转至leetcode

题目描述

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

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1:

输入:s = "()"
输出:true

示例 2:

输入:s = "()[]{}"
输出:true

示例 3:

输入:s = "(]"
输出:false

提示:

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

解法

方法一:栈

遍历括号字符串 \(s\),遇到左括号时,压入当前的左括号;遇到右括号时,弹出栈顶元素(若栈为空,直接返回 false),判断是否匹配,若不匹配,直接返回 false

也可以选择遇到左括号时,将右括号压入栈中;遇到右括号时,弹出栈顶元素(若栈为空,直接返回 false),判断是否是相等。若不匹配,直接返回 false

两者的区别仅限于括号转换时机,一个是在入栈时,一个是在出栈时。

遍历结束,若栈为空,说明括号字符串有效,返回 true;否则,返回 false

时间复杂度 \(O(n)\),空间复杂度 \(O(n)\)。其中 \(n\) 为括号字符串 \(s\) 的长度。文章来源地址https://www.toymoban.com/news/detail-496967.html

Python3

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False
        
        pairs = {
            ")": "(",
            "]": "[",
            "}": "{",
        }
        stack = list()
        for ch in s:
            if ch in pairs:
                if not stack or stack[-1] != pairs[ch]:
                    return False
                stack.pop()
            else:
                stack.append(ch)
        
        return not stack

C++

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};

到了这里,关于[Leetcode] 0020. 有效的括号的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcode刷题之有效的括号

    我们的内心和心智,是决定我们未来命运的最强劲的力量。         -- 奥普拉·温弗瑞 目录 🍁一.有效的括号 🍍1.使用栈实现 🍒2.完整代码: 题目描述: 给定一个只包括 \\\'(\\\',\\\')\\\',\\\'{\\\',\\\'}\\\',\\\'[\\\',\\\']\\\' 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 1.左括号必须用相

    2024年02月05日
    浏览(42)
  • LeetCode:20. 有效的括号——栈和队列

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 题目描述 :给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正

    2023年04月26日
    浏览(57)
  • Leetcode 678. 有效的括号字符串

    有效的括号字符串 【问题描述】 给你一个只包含三种字符的字符串,支持的字符类型分别是 ‘(’、‘)’ 和 ‘*’。请你检验这个字符串是否为有效字符串,如果是有效字符串返回 true 。 有效字符串符合如下规则: 示例 1: 输入:s = “()” 输出:true 示例 2: 输入:s = “

    2024年02月13日
    浏览(44)
  • 【动态规划】Leetcode 32. 最长有效括号【困难】

    给你一个只包含 ‘(’ 和 ‘)’ 的字符串,找出最长有效(格式正确且连续)括号子串的长度。 示例 2: 输入 :s = “)()())” 输出 :4 解释 :最长有效括号子串是 “()()” 1、使用动态规划求解,定义一个一维数组dp,其中dp[i]表示以第i个字符结尾的最长有效括号子串的长度

    2024年04月27日
    浏览(40)
  • 【刷题笔记8.10】LeetCode题目:有效括号

    给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号 首先,解决此题,我们要明确使用 栈

    2024年02月13日
    浏览(37)
  • 环形链表、环形链表 II、有效的括号​​​​​​​(leetcode)

    目录 一、环形链表 方法(快慢指针): 二、环形链表 II 三、有效的括号 给你一个链表的头节点  head  ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪  next  指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数  pos  来

    2024年02月04日
    浏览(40)
  • Leetcode的AC指南 —— 栈与队列:20. 有效的括号

    摘要: **Leetcode的AC指南 —— 栈与队列:20. 有效的括号 **。题目介绍:给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都

    2024年01月22日
    浏览(42)
  • 环形链表、环形链表 II、有效的括号​​​​​​​【LeetCode刷题日志】

    目录 一、环形链表 方法(快慢指针): 二、环形链表 II 三、有效的括号 给你一个链表的头节点  head  ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪  next  指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数  pos  来

    2024年02月03日
    浏览(42)
  • 【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号

    🌱 栈 是一种特殊的线性表, 只能在一端进行操作 🌱 往栈中 添加 元素的操作,一般叫做 push ( 入栈 ) 🌱 从栈中 移除 元素的操作,一般叫做 pop ,出栈(只能移除栈顶元素),也叫做: 弹出栈顶元素 🌱 后进先出 的原则, L ast I n F irst O ut, LIFO 注意:这里的 栈 与内

    2024年02月13日
    浏览(39)
  • 数据结构与算法之字符串: Leetcode 20. 有效的括号 (Typescript版)

    有效的括号 https://leetcode.cn/problems/valid-parentheses/ 描述 给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相

    2024年02月01日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包