leecode20.有效的括号使用python的题解

好的,我来为您介绍一下LeetCode第20题"有效的括号"的Python解法。

题目描述:
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足:
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 空字符串可被认为是有效字符串。

解题思路:
1. 使用栈结构来解决这个问题。
2. 遍历字符串中的每个字符。
3. 如果是左括号,将其压入栈中。
4. 如果是右括号,检查栈顶是否有对应的左括号:
- 如果栈为空,或者栈顶不是对应的左括号,返回False。
- 否则,弹出栈顶元素。
5. 遍历结束后,如果栈为空,说明所有括号都匹配,返回True;否则返回False。

下面是Python代码实现:

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        # 创建括号映射
        bracket_map = {')': '(', '}': '{', ']': '['}
        # 遍历字符串
        for char in s:
            if char in bracket_map:
                # 如果是右括号,检查栈顶是否有对应的左括号
                top_element = stack.pop() if stack else '#'
                if bracket_map[char] != top_element:
                    return False
            else:
                # 如果是左括号,压入栈中
                stack.append(char)
        # 如果栈为空,说明所有括号都匹配
        return not stack

这个解法的时间复杂度是O(n),因为我们只遍历了一遍字符串。空间复杂度是O(n),在最坏的情况下,栈中会存储字符串中所有的左括号。