题目

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

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

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

自解

def isValid(self, s: str) -> bool:
    while "()" in s or "{}"in s or "[]"in s:
        s = s.replace("()","")
        s = s.replace("{}","")
        s = s.replace("[]","")
    return not s

思路

如果是合理的字符组合（不为空）。
那么这个字符串只有两种情况：

• 字符串长度>0, 且必定存在必定存在子串’{}’或’()’或’[]’
  这种情况下，对子串’{}’或’()’或’[]’进行去除，能得到缩小了的同问题。
  不断重复去除的过程最终能使字符串长度==0.
• 字符串长度==0

时间复杂度：O(n²)

官方解法

def isValid(self, s):
        # 设置一个堆栈跟踪开括号
        stack = []

        # 哈希表 记录对应关系。这使得代码看起来非常干净。
        # 也使得增加更多类型的括号更容易
        mapping = {")": "(", "}": "{", "]": "["}

        # 遍历每个字符
        for char in s:
            # 如果是闭括号
            if char in mapping:
                # 如果栈非空，弹出最顶层元素
                # 否则将虚值"#"赋值给top_element
                top_element = stack.pop() if stack else '#'
                # 根据哈希表获取对应符号，如不符合对应，返回False
                if mapping[char] != top_element:
                    return False
            else:
                # 是开括号，压入栈中
                stack.append(char)

        # 如果在最后，栈是空的，那么匹配正确。
        # 如果栈不是空的，是出现了开括号多于闭括号的情况，如((()
        return not stack

时间复杂度：O(n)O(n)O(n)，因为我们一次只遍历给定的字符串中的一个字符并在栈上进行 O(1)O(1)O(1) 的推入和弹出操作。

算法

1. 初始化栈 S。
2. 一次处理表达式的每个括号。
3. 如果遇到开括号，我们只需将其推到栈上即可。这意味着我们将稍后处理它，让我们简单地转到前面的 子表达式。
4. 如果我们遇到一个闭括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号，那么我们将它从栈中弹出并继续处理。否则，这意味着表达式无效。
5. 如果到最后我们剩下的栈中仍然有元素，那么这意味着表达式无效。

---

• https://leetcode-cn.com/problems/valid-parentheses