letcode[020] 有效的括号

题目020

题目地址：有效的括号

思路1：自拟思路——替换法

首先替换掉字符串中所有空格，字符串长度不是2的整数倍则返回False。然后依次对字符串进行成对替换，直到字符串变为空，则返回True，如果字符串不为空且替换前后长度相等，则说明存在非配对括号，返回False
总结： 主要在于找准规律。
用时： 68 ms

s="(()[]{})"
s="([)]"
s="{([][](({}[([)])))}"
s="{([][](({ }[()])))}"
s=" "
def isValid1(s):
    s=s.replace(" ","")
    if len(s)%2!=0:
        return False
    while 1:
        before_length=len(s)
        s=s.replace("()","").replace("[]","").replace("{}","")
        after_length=len(s)
        if s=="":
            return True
        elif before_length==after_length:
            return False

思路2：网友思路——出入栈，根据顺序添加括号，有成对的则去除，直到列表为空

出入栈的思路，就是从左到右，将左括号放进一个列表（入栈），接下来找下一个括号，如果是左括号，则继续添加；如果是右括号则看它是否和前一个括号是配对的，配对则从列表中删除（出栈）；直到列表为空。
总结： 这个思路真线性。
用时： 48 ms

s="(){[]}"
def isValid2(s):
    if(len(s) % 2 == 1):
        return False
    x = ['[','(','{']
    y = ["]",")","}"]
    z = ["()","[]","{}"]
     
    res = []
    for i in s:
        print("i:"+i)
        if i in x:
            res.append(i) # 入栈
            print("res:")
            print(res)
        elif i in y:
            # 如果收到一个右括号，但是res中无左括号，直接返回False
            if res == []:
                return False
            else:
                temp = res.pop(-1) + i
                print("temp:"+temp)
                # 其余情况，出栈一个左括号，判断左括号+右括号是否有效
                if temp not in z:
                    return False
    return res == []

思路3：网友思路——用字典来进行出入栈（最快的）

还是进出栈的思路，换了哈希表（字典）的方式来执行。
总结： 这个return not stack写得可以说是传神了
用时： 36 ms

def isValid3(s):
    mapper = {')':'(', ']':'[', '}':'{'}
    stack = []
    for char in s:
        if char in mapper.values():
            stack.append(char)
        elif stack == [] or stack.pop() != mapper[char]:
            return False
    return not stack