0020. 有效的括号 #

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

题目大意 #

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s 。

要求：判断括号是否匹配。

解题思路 #

括号匹配是「栈」的经典应用。

我们可以用栈来解决这道题。具体做法如下：

先判断一下字符串的长度是否为偶数。因为括号是成对出现的，所以字符串的长度应为偶数，可以直接判断长度为奇数的字符串不匹配。
- 如果字符串长度为奇数，则说明字符串 s 中的括号不匹配，直接返回 False。
使用栈 stack 来保存未匹配的左括号。然后依次遍历字符串 s 中的每一个字符。
- 如果遍历到左括号时，将其入栈。
- 如果遍历到右括号时，先看栈顶元素是否是与当前右括号相同类型的左括号。
  - 如果是相同类型的左括号，则令其出栈，继续向前遍历。
  - 如果不是相同类型的左括号，则说明字符串 s 中的括号不匹配，直接返回 False。
遍历完，还要再判断一下栈是否为空。
- 如果栈为空，则说明字符串 s 中的括号匹配，返回 True。
- 如果栈不为空，则说明字符串 s 中的括号不匹配，返回 False。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False
        stack = list()
        for ch in s:
            if ch == '(' or ch == '[' or ch == '{':
                stack.append(ch)
            elif ch == ')':
                if len(stack) !=0 and stack[-1] == '(':
                    stack.pop()
                else:
                    return False
            elif ch == ']':
                if len(stack) !=0 and stack[-1] == '[':
                    stack.pop()
                else:
                    return False
            elif ch == '}':
                if len(stack) !=0 and stack[-1] == '{':
                    stack.pop()
                else:
                    return False
        if len(stack) == 0:
            return True
        else:
            return False