LeetCode-20 有效的括号

发表于 | 分类于 | 评论数： | 阅读次数：

题目：有效的括号

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

示例 1:

1
2
输入: "()"
输出: true

示例 2:

1
2
输入: "()[]{}"
输出: true

示例 3:

1
2
输入: "(]"
输出: false

示例 4:

1
2
输入: "([)]"
输出: false

示例 5:

1
2
输入: "{[]}"
输出: true

思路

这题可以通过堆栈的概念来解决，利用堆栈先进先出的特点实现

  • 先初始化一个括号对应关系的字典

  • 依次遍历字符串

  • 如果遇到左括号，则写入堆栈
  • 遇到非左括号的，则从堆栈中弹出最新写入的字符，比较是否成对
    • 成对的话，则匹配出了一个括号对，继续遍历
    • 如果当前堆栈还是空的，说明先出现右括号，直接返回False
    • 如果不成对，说明括号顺序有误，无法成对，返回False
  • 结束遍历时，如果堆栈已空说明全部成对，返回True，否则返回False

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def isValid(self, s: str) -> bool:
        flag_map = {'(': ')', '[': ']', '{': '}'}
        stack = []
        for char in s:
            if char in flag_map:
                stack.append(char)
            else:
                if stack:
                    element = stack.pop()
                    if flag_map[element] != char:
                        return False
                else:
                    return False
        return not stack

优化方法

把上述方法中的map进行反向，通过把右括号压入堆栈，来进行匹配，可以更简洁一点。

实现：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isValid(self, s: str) -> bool:
        flag_map = {")": "(", "}": "{", "]": "["}
        stack = []
        for char in s:
            if char in flag_map:
                element = stack.pop() if stack else '#'
                if flag_map[char] != element:
                    return False
            else:
                stack.append(char)
        return not stack

如果大家有更好的方法，欢迎一起探讨。