有效括号

Posted on Edited on In Word count in article: 636 Reading time ≈ 1 mins.
有效括号，栈的思路。入栈，出栈

问题

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isValid(self, s: str) -> bool:
        if s == "":
            return true
        if len(s) % 2 == 1:
            return False
        a = ["?"]
        dic = {")": "(", "]": "[", "}": "{", "?": "?"}
        for i in s:
            if i == "(" or i == "[" or i == "{":
                a.append(i)
            elif a.pop() != dic[i]:
                return False
        if len(a) != 1:
            return False
        return True

时间复杂度：O(n)，其中 n 是字符串 s 的长度。

空间复杂度：O(n+∣Σ∣)，其中Σ 表示字符集，本题中字符串只包含 6 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希映射使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度。