题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例：
输入：s = "([)]"
输出：false提示
一句话思路：用栈——遇到左括号入栈，遇到右括号检查栈顶是否匹配。
- 遇到左括号就入栈；遇到右括号时，栈不为空且栈顶恰好是对应左括号则出栈，否则无效。
- 用哈希表
dic建立「右括号 → 左括号」的映射，方便快速查找。 - 最终
not stack：栈为空说明所有左括号都被正确闭合，不为空则有未闭合的左括号。 - 时间 O(n)、空间 O(n)。
答案
python
class Solution:
def isValid(self, s: str) -> bool:
dic = {')': '(', ']': '[', '}': '{'} # 右括号到左括号的映射
stack = []
for i in s: # 遍历字符串每个字符
if stack and i in dic: # 栈非空 且 当前字符是右括号
if stack[-1] == dic[i]: # 栈顶是匹配的左括号
stack.pop() # 匹配成功，弹出栈顶
else: # 栈顶不是对应的左括号
return False # 不匹配，无效
else: # 栈为空 或 当前字符是左括号
stack.append(i) # 左括号入栈
return not stack # 栈为空说明全部匹配，有效
留言板