leetcode NO.20 有效的括号 腾讯精选练习50

题目描述

这道题我觉得挺难的，不知道为什么被标成了EASY，思索了许久发现也只有一种解法——暴力法

先放一下我自己初次的答案，由于不熟悉python的数据结构，写的长了很多
首先先理解题目的意思，怎么样才算是有效的括号，关键在于题目中的左括号要按照正确的顺序闭合
先用 a = [ ] 来记录这些个括号的进出，首先制定这样规则，进来的如果是左括号（有三种类型"（","[","{"）那就进入a。
如果a非空，也就是上面进来的左括号，如果下一个进来的右括号，我们检查这个进来的右括号是否对应 a[-1] （也就是最后一位）的左括号，如果是同一种括号，则删除 a 中 a[-1] 这个左括号。
如果进来的是左括号，那就和第一步一样，照常进入a。
这样扫描完全部的括号，如果 a == [ ] ，就说明这是有效的括号
如果非空，那么就是无效的括号。
现在我们来想想特殊的情况，如果第一个进来的是右括号，那么这必定是无效的。
那这种情况仅仅是对第一个进来的括号有用吗？不是的，只要前面是一个有效的括号（比如([])），再来一个右括号，必定是无效的，所以当a是空时，进来一个右括号必然无效。
这样整个思路就整理完了，我们再写一个输出对应括号的函数，就可以了。

class Solution:
    def isValid(self, s: str) -> bool:
        a = [] 
        for i in s:
            if i == "(" or i == "[" or i == "{":
                a = a + [i]
                continue
            else:
                if a == []:
                    return False
                else:
                    if self.reverse(a[-1]) == i:
                        a = a[:len(a)-1]
                        continue
                    else:
                        return False
        if a == []:
            return True
        else:
            return False
        
    def reverse(self,s:str) -> str:
        if s == "(":
            r = ")"
        elif s == "[":
            r = "]"
        elif s == "{":
            r = "}"
        else:
            r = s
        return r

事实上其实，并不需要reverse()这个函数，只需要一个字典来储存对应的右括号就可以了
改良后的代码如下，参考了大神的代码，思路是一样的，但是简洁了许多，通过append代替+，字典代替函数，使得速度有很大的提升。

class Solution:
    def isValid(self, s: str) -> bool:
        a = [] 
        dict = {'(': ')', '[': ']', '{': '}'}
        for i in s:
            if i == "(" or i == "[" or i == "{":
                a.append(i)
                continue
            else:
                if a == [] or dict[a.pop()] != i:
                    return False
        return a == []