专栏首页木又AI帮打卡群2刷题总结1005——有效的括号

打卡群2刷题总结1005——有效的括号


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. 柱状图中最大的矩形

解题思路:遍历元素,如果元素比栈顶元素更大,则压栈,否则不断弹栈。

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打卡群刷题总结0825——括号生成

    链接:https://leetcode-cn.com/problems/generate-parentheses

    木又AI帮
  • 打卡群刷题总结0626——括号生成

    链接:https://leetcode-cn.com/problems/generate-parentheses

    木又AI帮
  • 打卡群刷题总结1005——跳跃游戏

    链接:https://leetcode-cn.com/problems/jump-game

    木又AI帮
  • 打卡群2刷题总结1014——爬楼梯

    https://leetcode-cn.com/problems/climbing-stairs/

    木又AI帮
  • 打卡群2刷题总结1008——环形链表

    https://leetcode-cn.com/problems/linked-list-cycle/

    木又AI帮
  • 打卡群2刷题总结1007——反转链表

    https://leetcode-cn.com/problems/reverse-linked-list/

    木又AI帮
  • 打卡群2刷题总结1002——搜索插入位置

    https://leetcode-cn.com/problems/search-insert-position/

    木又AI帮
  • 打卡群刷题总结0824——电话号码的字母组合

    链接:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

    木又AI帮
  • 打卡群刷题总结0623——电话号码的字母组合

    链接:https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

    木又AI帮
  • 打卡群2刷题总结1010——二叉树的层序遍历

    https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

    木又AI帮
  • 打卡群2刷题总结1012——二叉树的最大深度

    https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

    木又AI帮
  • 打卡群2刷题总结1013——不同的二叉搜索树

    https://leetcode-cn.com/problems/unique-binary-search-trees/

    木又AI帮
  • 打卡群2刷题总结1009——二叉树的中序遍历

    https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

    木又AI帮
  • 打卡群2刷题总结1001——两数之和 II - 输入有序数组

    https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

    木又AI帮
  • 打卡群2刷题总结1003——搜索旋转排序数组

    https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

    木又AI帮
  • 打卡群2刷题总结1004——无重复字符的最长子串

    https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

    木又AI帮
  • 打卡群刷题总结0619——盛最多水的容器

    链接:https://leetcode-cn.com/problems/container-with-most-water/

    木又AI帮
  • 打卡群刷题总结0606——第一个错误的版本

    链接:https://leetcode-cn.com/problems/missing-number

    木又AI帮
  • 打卡群刷题总结0804——二叉树的中序遍历

    非递归解法,需要使用栈结构,同时使用一个visit数组标识该节点是否访问过其孩子节点。得到visit栈顶元素,判断是否访问过;如果访问过,则val加入到结果中;...

    木又AI帮

扫码关注云+社区

领取腾讯云代金券