leetcode[20]-有效的括号

题目

给定一个只包括 ‘(‘,’)’,'{‘,’}’,'[‘,’]’ 的字符串,判断字符串是否有效。有效字符串需满足: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='',也就是你在根据索引取值就要报错,但是网站没有此类测试数据。

发表评论

电子邮件地址不会被公开。