leetcode20.有效的括号

发布于 2021-04-17 05:33 ，所属分类：知识学习综合资讯

题目描述

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

有效字符串需满足：

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

示例

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

（左右滑动查看完整内容）

提示

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

难度：简单
标签：栈、字符串

分析和题解

方法一

1.字符串s 仅由括号'()[]{}'组成，且有效字符串左括号必须用相同类型的右括号闭合，所以有效字符串的长度一定为偶数，如果为奇数可以直接返回False，省去后续的判断过程。

2.当遇到左括号时，会期望在字符串s后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合（先进后出），所以可以将这个左括号放入栈顶。

3.当遇到右括号时，需要将一个相同类型的左括号闭合。此时可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果栈中没有左括号了，或者它们不是相同的类型，那么字符串 s无效，返回 False。

4.为了快速判断括号的类型，可以使用字典（哈希表）存储每一种括号。字典的键为左括号，值为相同类型的右括号。

5.在遍历结束后，如果栈中没有左括号，说明将字符串 s 中的所有左括号闭合，返回True，否则返回 False。

class Solution:    def isValid(self, s: str) -> bool:        if len(s) % 2 == 1:  # 有效字符串的长度一定为偶数，如果为奇数可以直接返回False，省去后续的判断过程            return False            dic = {'(': ')', '[': ']', '{': '}'}        left = []  # 栈，存放左括号        for i in s:  # 遍历字符串s            if i in dic:  # 左括号                left.append(i)  # 左括号放入栈顶            else:  # 右括号                if not left or dic[left.pop()] != i:  # 没有对应的左括号                    return False        return not left  # left为空返回True

（左右滑动查看完整代码）

方法二

1.有效字符串的长度一定为偶数，如果为奇数可以直接返回False，省去后续的判断过程。

2.对于有效的字符串，部分子表达式仍然是有效的，如 {()[()]} 是有效的，()[{}] 是有效的，[()] 也是有效的。并且每次删除一个成对的括号时，会逐渐将括号全部删除完；如果没有删除完，那一定是无效的字符串。

class Solution:  def isValid(self, s: str) -> bool:    if len(s) % 2 == 1: # 有效字符串的长度一定为偶数，如果为奇数可以直接返回False，省去后续的判断过程      return False
    while '()' in s or '[]' in s or '{}' in s:      s = s.replace('()', '').replace('[]', '').replace('{}', '') # 多次循环把字符串中成对的括号去掉    return not s