LeetCode | 有效的括号

分类：栈

题目#

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

有效字符串需满足：

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

示例 1：

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

示例 2：

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

讲解#

括号匹配是栈的经典应用。从左到右扫描字符串，用一个字典 pairs 存右括号到左括号的映射。

遇到左括号（不在 pairs 中）：入栈。遇到右括号：检查栈是否为空，或者栈顶是否匹配 pairs[ch]。不匹配直接返回 False。

提前判断：字符串长度是奇数直接返回 False，因为有效的括号一定是成对出现。

最后栈必须为空，才算全部匹配。

复杂度#

暴力做法：不断替换 "()"、"[]"、"{}" 直到字符串不再变化，时间复杂度 O(n²)。
栈：
- 时间复杂度：O(n)
- 空间复杂度：O(n)

代码#

源码#

1
class Solution:
2
    def isValid(self, s: str) -> bool:
3
        if len(s) % 2 == 1:
4
            return False
5

6
        pairs = {')': '(', ']': '[', '}': '{'}
7
        stack = []
8

9
        for ch in s:
10
            if ch not in pairs:
11
                stack.append(ch)
12
            elif not stack or stack.pop() != pairs[ch]:
13
                return False
14

15
        return not stack

测试#

1
sol = Solution()
2

3
assert sol.isValid("()") == True
4
assert sol.isValid("()[]{}") == True
5
assert sol.isValid("(]") == False
6
assert sol.isValid("([])") == True
7
assert sol.isValid("([)]") == False
8
assert sol.isValid("{[]}") == True
9
assert sol.isValid("") == True
10
assert sol.isValid("((") == False
11

12
print("PASS")

参考资料#

力扣原题：https://leetcode.cn/problems/valid-parentheses/
题解参考：https://github.com/doocs/leetcode/blob/main/solution/0000-0099/0020.Valid%20Parentheses/README.md

音乐

音乐

题目#

讲解#

复杂度#

代码#

源码#

测试#

参考资料#

文章分享

评论区

音乐

文章目录