LeetCode 20. Valid Parentheses 题解

LeetCode 20. Valid Parentheses 题解题目描述给定一个只包括(){}[]的字符串s判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。示例 1输入s () 输出true示例 2输入s ()[]{} 输出true示例 3输入s (] 输出false示例 4输入s ([)] 输出false示例 5输入s {[]} 输出true解题思路方法栈思路使用栈来存储左括号遍历字符串中的每个字符如果是左括号将其压入栈中如果是右括号检查栈是否为空如果栈为空返回 false否则弹出栈顶元素检查是否与当前右括号匹配如果不匹配返回 false遍历结束后检查栈是否为空如果栈为空返回 true否则返回 false复杂度分析时间复杂度O(n)其中 n 是字符串的长度。每个字符只被处理一次。空间复杂度O(n)其中 n 是字符串的长度。最坏情况下栈的大小为 n。代码实现方法栈class Solution: def isValid(self, s: str) - bool: # 括号映射表 bracket_map { ): (, }: {, ]: [ } stack [] for char in s: # 如果是右括号 if char in bracket_map: # 检查栈是否为空 if not stack: return False # 弹出栈顶元素检查是否匹配 top stack.pop() if top ! bracket_map[char]: return False # 如果是左括号压入栈中 else: stack.append(char) # 遍历结束后检查栈是否为空 return not stack测试用例测试用例 1输入s ()输出true测试用例 2输入s ()[]{}输出true测试用例 3输入s (]输出false测试用例 4输入s ([)]输出false测试用例 5输入s {[]}输出true总结本题是栈的经典应用问题主要考察对栈数据结构的理解和使用。通过使用栈来存储左括号我们可以有效地检查括号是否匹配。栈的核心思想是后进先出LIFO这使得它非常适合解决括号匹配问题。当遇到左括号时我们将其压入栈中当遇到右括号时我们从栈中弹出栈顶元素并检查是否与当前右括号匹配。这种方法不仅适用于括号匹配问题还可以应用于许多其他需要后进先出特性的问题例如表达式求值、函数调用栈等。掌握栈的使用对于解决这类问题非常重要。