20. 有效的括号

20. 有效的括号

2022年11月4日

---

一、问题描述

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

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true
1
2

示例 2：

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

示例 3：

输入：s = "(]"
输出：false
1
2

提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

二、问题分析

• 算法思路如下：
  

三、解题代码

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        dic = {')':'(', ']':'[', '}':'{'}
        for ch in s:
            if ch in ['(', '[', '{']:
                stack.append(ch)
            else:
                if len(stack) == 0 or stack[-1] != dic[ch]:
                    return False
                else:
                    stack.pop()
        if len(stack) == 0:
            return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

总结

使用栈对左括号进行存储，每次遇到右括号就判断栈顶元素是否为与之匹配的左括号，不匹配返回Flase，匹配则弹栈然后继续判断，直到遍历字符串结束，若栈空则返回True，反之返回False。