验证是否为有效括号

Question: 验证是否为有效括号

👉LeetCode链接👈

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

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

Example

1
2
"()[]{}" 为有效关闭
"([)]" 为错误

Answer

1
2
3
4
5
6
7
8
9
10
11
12
def isValid(s):
    stack = []
    dict = {"]":"[", "}":"{", ")":"("}
    for char in s:
        if char in dict.values():
            stack.append(char)
        elif char in dict.keys():
            if stack == [] or dict[char] != stack.pop():
                return False
        else:
            return False
    return stack == []

Finally

使用入栈，出栈的方式来进行判断

  1. 循环，将遇到的所有的正括号都入栈
  2. 直到遇到反括号，遇到反括号时
    1. 判断栈是否为空，为空的话说明栈里没有与之匹配的正括号，说明是非法字符串
    2. 再将栈顶的括号取出来，判断是否与之匹配
      1. 匹配的话，也就是成功去掉了一对正确的括号
      2. 否则，说明是非法字符串
  3. 最后循环完毕还没有匹配失败的话
  4. 再判断栈里面是否还有括号，有的话为非法字符串