题目
给定一个只包括 ‘(‘,’)’,'{‘,’}’,'[‘,’]’ 的字符串,判断字符串是否有效。有效字符串需满足:1、左括号必须用相同类型的右括号闭合。2、左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。
python代码
class Solution(object):
def trans(self,t):
if t=='(':
return 1
elif t==')':
return -1
elif t=='[':
return 2
elif t==']':
return -2
elif t=='{':
return 3
elif t=='}':
return -3
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
len_s = len(s)
if len_s%2!=0:
return False
if s=='':
return True
if self.trans(s[0])<0:
return False
left_s=''
for i in xrange(len_s):
if self.trans(s[i])>0:
left_s+=s[i]
elif self.trans(s[i])<0 and len(left_s)>=1:
if self.trans(s[i])+self.trans(left_s[-1])==0:
if len(left_s)==1:
left_s=''
else:
left_s=left_s[:-1]
else:
return False
else:
return False
if left_s=='':
return True
else:
return False
well,well,well,这个题目重点应该不再算法上,而是在编程实现上,思路很明确,就是左括号不能出现在对应右括号的右边,括号必须成对出现。
def trans(self,t):
if t=='(':
return 1
elif t==')':
return -1
elif t=='[':
return 2
elif t==']':
return -2
elif t=='{':
return 3
elif t=='}':
return -3
这个函数将字符转换为了数字,以便于判断是否配对问题,这个我感觉应该是最直观的方法吧,左括号为一个正数,右括号为负数,对应的相加刚好为0。
len_s = len(s)
if len_s%2!=0:
return False
if s=='':
return True
if self.trans(s[0])<0:
return False
这里我考虑了三种特殊情况,1、长度不是偶数的话,那肯定至少有一组没有配对。2、根据题目要求。3、如果第一个括号为右括号的话,也是直接返回错误,因为违法了顺序规则。
for i in xrange(len_s):
if self.trans(s[i])>0:
left_s+=s[i]
elif self.trans(s[i])<0 and len(left_s)>=1:
if self.trans(s[i])+self.trans(left_s[-1])==0:
if len(left_s)==1:
left_s=''
else:
left_s=left_s[:-1]
else:
return False
else:
return False
ps:第一次提交这次题目时候写了一个有bug的程序,但是通过了,已经反馈到他们网站,这里是修正后的程序。
– 这段程序是算法的精髓,首先我们至少要把字符串遍历一遍,我们使用了一个新的字符串left_s
用来保存左括号,意思就是我从头开始遍历s
,遇到左括号就放进left_s
,遇到右括号我先判断是不是和left_s
最后面的是对应的,如果是那么就抵消,继续往后遍历,如果不对应,则结束。
– 这里还有点要注意的,之前的错误就是在if self.trans(s[i])+self.trans(left_s[-1])==0:
时,没有提前判断left_s
的长度,如果刚好在此时之前都成功配对,那么left_s=''
,也就是你在根据索引取值就要报错,但是网站没有此类测试数据。