题目
-
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
法一：栈
- 思路：遇到左括号就入栈，遇到右括号先判断栈里还有元素没，如果没了直接返回False，其次判断栈顶元素是否匹配，不匹配直接返回false，如果匹配就出栈。遍历完整个字符串后检查栈是否为空，不为空返回False
class Solution:
def isValid(self, s: str) -> bool:
res = [] # 用于存储左括号的栈
i = 0 # 用于遍历字符串的索引
while i < len(s):
if s[i] == '(' or s[i] == '[' or s[i] == '{':
res.append(s[i]) # 遇到左括号，将其加入栈中
elif s[i] == ')':
if len(res) == 0 or res[-1] != '(': # 遇到右括号')'，判断栈顶元素是否为对应的左括号'('，如果不是则返回False
return False
res.pop() # 栈顶元素为对应的左括号'('，出栈
elif s[i] == ']':
if len(res) == 0 or res[-1] != '[': # 遇到右括号']'，判断栈顶元素是否为对应的左括号'['，如果不是则返回False
return False
res.pop() # 栈顶元素为对应的左括号'[', 出栈
elif s[i] == '}':
if len(res) == 0 or res[-1] != '{': # 遇到右括号'}'，判断栈顶元素是否为对应的左括号'{'，如果不是则返回False
return False
res.pop() # 栈顶元素为对应的左括号'{', 出栈
else:
return False # 如果遇到非括号字符，直接返回False
i += 1 # 继续遍历字符串的下一个字符
if len(res)!=0:
return False
return True # 遍历完字符串后，检查栈是否为空，如果栈为空，说明所有括号都匹配，返回True；否则返回False
法二：字典
class Solution:
def isValid(self, s: str) -> bool:
dic = {')': '(', ']': '[', '}': '{'}# 使用字典存储右括号与对应的左括号的映射关系
stack = []# 使用栈来存储左括号
for char in s:# 遍历字符串中的每个字符
if char in dic.values():# 如果当前字符是左括号，直接入栈
stack.append(char)
elif char in dic: # 如果当前字符是右括号
if not stack or stack[-1] != dic[char]:# 如果栈为空或栈顶元素与当前字符不匹配，则返回 False
return False
else: # 匹配成功，将栈顶元素出栈
stack.pop()
else: # 如果不是括号字符
return False
return not stack # 最后，如果栈为空，表示所有括号都匹配，返回 True；否则，返回 False