题目描述

[EN | CN]

给定一个只包括 '('')''{''}''['']' 的字符串,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。

  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

1
2
输入: "()"
输出: true

示例 2:

1
2
输入: "()[]{}"
输出: true

示例 3:

1
2
输入: "(]"
输出: false

示例 4:

1
2
输入: "([)]"
输出: false

示例 5:

1
2
输入: "{[]}"
输出: true

解法 1:栈

判断括号是否配对,这道题应该挺常见的,应该用 来解。这里有几个值得注意的地方:

  • 该字符串的长度一定是偶数,否则返回 False。
  • 遍历时如果遇到左符号则压入栈,遇到右符号则判断与栈顶是否匹配,匹配则弹出,继续往下;若不匹配则返回 False。
  • 当遍历完字符串时,栈应该为空,否则返回 False。

假设字符串长度为 $n$,那么

  • 时间复杂度为 $O(n)$,需要遍历一遍;
  • 空间复杂度为 $O(n)$,需要压入栈。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 != 0:
            return False

        stack = []
        for char in s:
            if char in ['(', '[', '{'] or len(stack) == 0:
                stack.append(char)
            elif (stack[-1] == '(' and char == ')'
                or stack[-1] == '[' and char == ']'
                or stack[-1] == '{' and char == '}'):
                stack.pop()
            else:
                return False

        return len(stack) == 0
  • 执行用时:44 ms,在所有 Python3 提交中击败了 42.21% 的用户。
  • 内存消耗:13.8 MB,在所有 Python3 提交中击败了 5.34% 的用户。

解法 2:迭代消除最中间的括号

一个比较讨巧的方法。如果该字符串的括号有效,那么中间必定至少有一对相邻且配对的括号(即「()」、「{}」、「[]」),我们利用这点可以使用迭代来不断消掉这种相邻且配对的括号,当消到最后时(终止条件为找不到这样的符号了),该字符串若为空串,则说明有效。

假设字符串长度为 $n$,那么

  • 时间复杂度为 $O(n)$,光是 replace 方法就需要 $O(n)$ 时间,注意尽管复杂度看起来还行,但实际运行起来肯定是效率不高的;
  • 空间复杂度为 $O(1)$,不需要额外的空间。

实现与结果如下:

1
2
3
4
5
6
7
8
9
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) == 0:
            return True
        if len(s) % 2 != 0:
            return False
        while '()' in s or '{}' in s or '[]' in s:
            s = s.replace('()', '').replace('{}', '').replace('[]', '')
        return s == ''
  • 执行用时:52 ms,在所有 Python3 提交中击败了 24.46% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 5.34% 的用户。