题目

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

有效字符串需满足：

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

解题思路

匹配失败的情况

  1. 左括号多了 例如

    ​ image.png

  2. 右括号多了 例如

    ​

    ​

  3. 括号不匹配 例如

    ​ image.png

排除掉上面的是那种匹配失败的情况之后，剩余的都是匹配成功

思路

核心思想是利用栈去匹配括号

用字典构造一个哈希表，表示右括号对应的左括号

1
dic = {'}':'{',']':'[',')':'('}

用一个字符串表示左括号

1
kuohao = '{(['

我的解法

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
28
29
30
31
32
class Solution:
    def isValid(self, s: str) -> bool:
        # 括号匹配问题 使用栈来匹配
        s = list(s)
        dic = {'}':'{',']':'[',')':'('}
        kuohao = '{(['
        stack = []
        for i in s:
            # 如果stack为空的话，则入栈 这种情况排除第一个就是右括号的情况
            # print(stack)          
            if not stack:
                stack.append(i)
                continue
            # 如果是左括号则入栈
            if i in kuohao:
                stack.append(i)
            else:
                # print('dic[i] is ', dic[i])
                # 哈希表中对应的值与栈尾元素进行比较
                if dic[i]==stack[-1]:
                    # 括号匹配成功之后则弹出栈
                    stack.pop()
                else:
                    # 匹配不成功则是匹配失败的第三种情况
                    return False
        # print('stack is ',stack)
        # 如果stack栈不为空的话则是匹配失败的第一种和第二种情况
        if stack:
            return False
        # 排除三种异常情况之外则匹配成功
        else:
            return True