有效的括号

Leetcode Link: 20. 有效的括号 - 力扣（LeetCode）

题目

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

有效字符串需满足：

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

解法一

思路：自己想的暴力解法，举几个例子来分析情况，

1. "([)]" 应该是 False → 要用栈的结构存储，不能用字典
2. "(" 应该是 False → 要在最后判断栈是否为空

题解：

class Solution:
    def isValid(self, s: str) -> bool:
        stack = collections.deque()
        for c in s:
            if c == ")" and len(stack)>0:
                t = stack.pop()
                if t != "(":
                    return False
            elif c == "]" and len(stack)>0:
                t = stack.pop()
                if t != "[":
                    return False
            elif c == "}" and len(stack)>0:
                t = stack.pop()
                if t != "{":
                    return False
            else:
                stack.append(c)
        if len(stack) != 0:
            return False
        else:
            return True

---

复习时的新代码

class Solution:
    def isValid(self, s: str) -> bool:
        bucket = []
        for c in s:
            if c in '[({':
                bucket.append(c)
            elif c == ']':
                if len(bucket) == 0 or bucket.pop() != '[':
                    return False
            elif c == '}':
                if len(bucket) == 0 or bucket.pop() != '{':
                    return False
            elif c == ')':
                if len(bucket) == 0 or bucket.pop() != '(':
                    return False
        return True if len(bucket)==0 else False

复习时发现两个注意的点

1. 每次pop要判断是不是空
2. 最后要判断栈是不是空

解法二

思路：来源

一定至少有一个是紧紧挨着的 (), 或者 [], 或者 {}

我们从这里开始，不断删除掉”紧紧挨着的”这些括号，如果有错误，那么一定无法全部删除，删除之后的字符串一定不是空的，因此最后判断是不是为空就可以

这个方法真的巧！

题解：

class Solution:
    def isValid(self, s):
        while '{}' in s or '()' in s or '[]' in s:
            s = s.replace('{}', '')
            s = s.replace('[]', '')
            s = s.replace('()', '')
        return s == ''

注意 s.replace() 不是原地替换，需要有变量接受输出

启发和联系

括号问题考虑栈。