有效括号相关

相关题目
20. 有效的括号
921. 使括号有效的最少添加
1541. 平衡括号字符串的最少插入次数
32. 最长有效括号

# 20. 有效的括号
class Solution:def isValid(self, s: str) -> bool:stack = []for pare in s:if pare in '([{':stack.append(pare)if not stack or (pare == ')' and stack[-1] != '('):return Falseelif not stack or (pare == ']' and stack[-1] != '['):return Falseelif not stack or (pare == '}' and stack[-1] != '{'):return Falseif pare in ')]}':stack.pop()return not stack

# 921. 使括号有效的最少添加
class Solution:def minAddToMakeValid(self, s: str) -> int:# 对左括号的需求res = 0# 对右括号的需求need = 0for c in s:if c == '(':# 右括号需求need += 1else:need -= 1if need == -1:need = 0# 需要插入一个左括号res += 1return res + need

# 1541. 平衡括号字符串的最少插入次数
class Solution:def minInsertions(self, s: str) -> int:# 对左括号的需求res = 0# 对右括号的需求need = 0for c in s:if c == '(':# 右括号需求need += 2if need % 2 == 1:# 插入一个右括号res += 1# 右括号需求减1need -= 1else:need -= 1if need == -1:# 需要插入一个左括号res += 1# 同时右括号的需求变为1need = 1return res + need

# 32. 最长有效括号
# 动态规划+栈
class Solution:def longestValidParentheses(self, s: str) -> int:# dp[i] 表示已s[i-1]结尾的最长合法括号子串的长度dp = [0] * (len(s) + 1)stk = []for idx, c in enumerate(s):if c == '(':# 遇到左括号，记录索引stk.append(idx)# 左括号结尾，不可能是有效合法括号dp[idx+1] = 0else:if stk:# 配对的左括号对应索引leftIndex = stk.pop()dp[idx+1] = (idx - leftIndex + 1) + dp[leftIndex]else:dp[idx+1] = 0return max(dp)