Easy 6 – 有效的括号

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

第一版代码:

class Solution:
    def isValid(self, s: str) -> bool:
        brace_dic = {"(":1, ")":1, "[":2, "]":2, "{":3, "}":3}
        trans_s = []
        for c in s:
            trans_s.append(brace_dic[c])
        if trans_s == trans_s[::-1]:
            return True
        else:
            return False

感觉还挺对的,结果一试,出错了。例如”()[]{}”会被认为是错误的。还是对题目的理解出了一定的差池。

上午又想了想应该怎么办,又做了一版代码出来:

class Solution:
    def isValid(self, s: str) -> bool:
        brace_dic = {"(":1, ")":-1, "[":2, "]":-2, "{":3, "}":-3}
        length = len(s) - 1
        while s != "":
            for position, char in enumerate(s):
                if position < length:
                    if brace_dic[s[position+1]] < 0:
                        if brace_dic[s[position]] + brace_dic[s[position+1]] == 0:
                            s = s[:position] + s[position:]
                        else:
                            return False
        return True

大概的逻辑是这样的:

根据括号的左右半边进行赋值,左边是某个正数(1,2,3),右边是其对应的负数(-1,-2,-3)。在没有遇到负数之前,先进行遍历,一旦出现负数,那就立刻查询负数前的数与其只和是否为0,如果是0,则说明两个是一对,然后从原字符串中进行剔除,再次进行判断,只要有一个和不是0,则说明不是一对。这个方法会出现out of range的问题,困扰了我蛮久。

再一想,TMD我往前比不就没有这个问题了吗?猪脑属实过载了。

再写一版:

for position, char in enumerate(s):
    if brace_dic[char] < 0:
        if position == 0:
            print('False')
        if brace_dic[char] + brace_dic[s[position-1]] == 0:
            s = s.replace(s[position], "")
            print(s)
        else:
            print('False')

这一版还是有问题的,replace这里我还是没找到合适的办法来把这两个数字去掉,我不是很想看答案,再给自己一上午的时间看能不能想出来吧。

胜负欲这种东西太可怕了,不甘心就这么睡了,又想了想写成了下面这个样子:

class Solution:
    def isValid(self, s: str) -> bool:
        brace_dic = {"(":1, ")":1, "[":2, "]":2, "{":3, "}":3}
        trans_s = []

        for char in s:
            trans_s.append(brace_dic[char])
        
        while trans_s:
            for position, number in enumerate(trans_s):
                if number < 0:
                    if position == 0:
                        return False
                    if number + trans_s[position-1] == 0:
                        trans_s[position], trans_s[position-1] = 0, 0
                    else:
                        return False
                if number == 0:
                    trans_s.remove(0)
        return True

在本地上跑了几个例子,是没啥问题的,但是在leetcode上跑就显示超时,看后续还能不能有改进。

今天终于有时间来看这道题。

后来是和耀伦聊了聊,确实专业的就是不一样嗷,我之前的思路可能确实是对的但是对数据结构的思考还是不够彻底,聊完之后又试着写了一版:

class Solution:
    def isValid(self, s: str) -> bool:
        brace_dic = {")":"(", "]":"[", "}":"{"}
        
        temp_s = []

        for position, char in enumerate(s):
            if char in "({[":
                temp_s.append(char)
            else:
                if temp_s == []:
                    return False
                else:
                    if brace_dic[char] == temp_s[-1]:
                        del temp_s[-1]
                    else:
                        return False

        if temp_s == []:
            return True
        else:
            return False

虽然看起来有些麻烦但是确实是我能想到的极限了。这个想法还是有些巧思的,比如把正反括号作为词典的key和value以及用堆栈的思想来解决这个问题(虽然我一开始的想法就是朴素的堆栈概念但是我真的忘了这个名词)。

最后是可以跑通的,但是内存占用比较大,只打败了20%的用户。

看了看评论区,确实思路是对的,只是我写的比较零碎,再稍微优化一下可能更好些。

Leave a Reply