Easy 20 – 有效的括号
给定一个只包括 ‘(‘,’)’,'{‘,’}’,'[‘,’]’ 的字符串 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