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='',也就是你在根据索引取值就要报错，但是网站没有此类测试数据。