这道题是菜鸡开始刷题的时候碰到的第一个小坎儿。刚开始几次 submmit 都没有成功。经过几次错误分析,发现题目要求的正确的字符串有几个特点:

  • 字符个数为偶数

  • 正确的字符串不管内容如何排布,总会有成对的括号在一起,一步步消除这种成对的括号,以及因为消除出现的新的成对括号,整个字符串就会消空。

基于上面两个特点,我自己编写了一个解法,可以说是惨不忍睹。但还是要贴出来以与后来的别人的简洁解法作对比:

class Solution(object):

    def isPare(self, before, next):
        if before == '[' and next == ']':
            return 1
        if before == '{' and next == '}':
            return 1
        if before == '(' and next == ')':
            return 1
        return 0

    def popPare(self, s):
        i = 0
        while len(s)> 2:
            if self.isPare(s[i], s[i+1]):
                s.pop(i)
                s.pop(i)
                if i == 0:
                    i = -1
                else:
                    i = i - 2
            i = i + 1
            if i > len(s) - 2:
                break
        return s

    def isValid(self, s):
        """
        :param s: str
        :return: bool
        """
        s = list(s)
        if len(s) % 2 != 0:
            return False
        s = self.popPare(s)
        if len(s) != 2:
            return False
        elif self.isPare(s[0], s[1]):
            return True
        else:
            return False

我写了三个函数,第一个是用来检测字符配对,但这个其实用一个简单的词典就能完成。我真是傻。

第二个用来检测所给字符串中相邻的字符是否配对,配对则消去。

在消去字符的时候我刚开始用的是 remove 方法。我发现这个 remove 方法是根据传入内容从左开始的,这意味着重复的字符串里,remove 的可能是左边的重复字符。后来还是用了 pop 函数,用了 pop 函数的时候我竟然还没有想到这道题可以用 stack 来快速解决啊。我真是傻。

第三个就是判断函数,没啥好说的。

好了,下面贴一个别人的 python 答案,使用了 stack, 很简洁。

class Solution:
    # @return a boolean
    def isValid(self, s):
        stack = []
        dict = {"]":"[", "}":"{", ")":"("}
        for char in s:
            if char in dict.values():
                stack.append(char)
            elif char in dict.keys():
                if stack == [] or dict[char] != stack.pop():
                    return False
            else:
                return False
        return stack == []

前路还有很远。加油。