20. 有效的括号

class Solution:

    def isValid(self, s: str) -> bool:

        dic = {'{': '}',  '[': ']', '(': ')', '?': '?'}

        stack = ['?']

        for c in s:

            if c in dic:

                stack.append(c)

            elif dic[stack.pop()] != c:

                return False

        return len(stack) == 1

一、代码整体功能：
这段代码定义了一个名为 Solution 的类，其中包含一个名为 isValid 的方法，该方法用于检查输入的字符串 s 是否是一个有效的括号序列。有效括号序列是指，每个左括号都能找到与之匹配的右括号，并且它们的顺序是正确的。

二、代码结构分析：

1. 字典 dic 的创建：

   dic = {'{': '}',  '[': ']', '(': ')', '?': '?'}

   这个字典存储了左括号作为键，右括号作为对应的值。这里添加了一个特殊的键值对 '?' : '?'，是为了在初始化栈时，防止栈为空而导致的 pop 操作错误。

2. 栈 stack 的初始化：

   stack = ['?']

   栈是用来存储左括号的。初始化时将 '?' 压入栈中，主要是为了避免在后面的操作中，对空栈进行 pop 操作而引发异常。

3. 遍历输入字符串 s：

   for c in s:

   使用 for 循环遍历输入字符串中的每个字符。

4. 处理左括号：

   if c in dic:
       stack.append(c)

   如果当前字符 c 是字典 dic 中的键（即左括号），将其压入栈 stack 中。

5. 处理右括号并检查匹配性：

   elif dic[stack.pop()]!= c:
       return False

   如果当前字符 c 不是左括号，那么它应该是右括号。此时从栈中弹出一个元素，使用 stack.pop() 方法，并通过 dic[stack.pop()] 查找其对应的右括号，将其与当前字符 c 比较。如果不相等，说明不匹配，返回 False。

6. 最终检查：

   return len(stack) == 1

   当遍历完字符串 s 后，栈中应该只留下初始添加的 '?' 元素，此时栈的长度为 1。如果长度不为 1，说明存在未匹配的左括号，返回 False；如果长度为 1，则认为输入的括号序列是有效的，返回 True。

三、总结：
这段代码利用栈和字典的数据结构，巧妙地实现了对括号序列有效性的检查。通过将左括号压入栈中，遇到右括号时从栈中弹出相应的左括号进行匹配检查，最终根据栈的状态来判断括号序列是否有效。这种方法的时间复杂度是 $O(n)$，因为需要遍历输入字符串中的每个字符。空间复杂度主要取决于栈的最大长度，最坏情况下为 $O(n)$，因为可能将整个输入字符串中的左括号都压入栈中。

以下是一个使用示例：

sol = Solution()
print(sol.isValid("()[]{}"))  # 输出: True
print(sol.isValid("([)]"))  # 输出: False

在这个示例中，首先创建了 Solution 类的实例 sol，然后调用 isValid 方法，分别传入不同的字符串，检查它们是否是有效的括号序列。对于 "()[]{}" 这个字符串，左括号和右括号都能正确匹配，所以返回 True；而对于 "([)]" 这个字符串，由于括号的匹配顺序错误，返回 False。