20. 有效的括号-栈的应用

20. 有效的括号

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

解题思路

当开始接触题目时，我们会不禁想到如果计算出左括号的数量，和右括号的数量，如果每种括号左右数量相同，会不会就是有效的括号了呢？

事实上不是的，假如输入是 [{]}，每种括号的左右数量分别相等，但不是有效的括号。这是因为结果还与括号的位置有关。

仔细分析我们发现，对于有效的括号，它的部分子表达式仍然是有效的括号，比如 {()[()]} 是一个有效的括号，()[{}] 是有效的括号，[()] 也是有效的括号。并且当我们每次删除一个最小的括号对时，我们会逐渐将括号删除完。比如下面的例子。

这个思考的过程其实就是栈的实现过程。因此我们考虑使用栈，当遇到匹配的最小括号对时，我们将这对括号从栈中删除（即出栈），如果最后栈为空，那么它是有效的括号，反之不是。

实现代码：

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        dic = {')':'(',']':'[','}':'{'}
        for i in s:
            if(stack and i in dic):#i in dic表示, i在{')',']','}'}范围内
                if(stack[-1] == dic[i]):#当栈顶字符和i遍历到的字符配对时
                    stack.pop()#弹出栈顶元素
            #每当匹配到{')',']','}'}时，该位置的左侧必然会一个能匹配的字符，否则匹配不成功
                else: return False
            else:
                stack.append(i)
        return len(stack) == 0

参考：力扣 

下面还有一个更加简单的做法：

就先找到那个最小的能够匹配字符串，然后用空字符('')把它替换掉，接着再在新的字符串里找能都匹配的最小字符串，再用''把它替换掉，如果到最后最初的字符串变成空字符'',那么就说明是有效的括号。

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