有效的括号问题
问题描述:
思路1的解决方案要比思路2的解决方案运行效率更高,所以不能一味的追求python的简洁,要在调库的基础上也有基本的算法思想!
思路1:
类似栈的思想,碰到左括号进栈。右括号进行判断:如果和左括号匹配,则退栈,不匹配直接报错。
我是新建一个列表,碰到左括号保存,右括号进行判断,如果和左括号匹配则删除新建列表的左括号,不匹配则报错。其中需要判断碰到右括号时,新建列表是否有元素。这样做的目的是防止新建列表这个时间点为空,判断s[i-1]是否为对应的左括号时出现越界异常。
思路2:
基于python。python中有判断一个字串是否在另一个字串中的功能。比如
因此可以直接判断'()'、'[]'或者'{}'是否在给出的符号字符串中并用replace替代为空,如下:
代码1:
class Solution:
def isValid(self, s: str) -> bool:
temp = []
for ch in s:
if ch == '(' or ch == '[' or ch =='{':
temp.append(ch)
elif ch == ')':
if len(temp) == 0 or temp[-1] != '(':
return False
else:
del temp[-1]
elif ch == ']':
if len(temp) == 0 or temp[-1] != '[':
return False
else:
del temp[-1]
elif ch == '}':
if len(temp) == 0 or temp[-1] != '{':
return False
else:
del temp[-1]
if len(temp) == 0:
return True
else:
return False
代码2:
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 == ''