APP
一、有效的括号
此题在《数据结构与算法——栈与队列》中出现
二、括号生成
此题在《数据结构与算法——广度优先与深度优先搜索》中出现
三、最长有效括号
此题为leetcode第32题
思路：考虑使用动态规划，定义状态dp[i]为以第i个元素结尾的最长有效括号的长度。有效的括号一定是以“）”结尾的，因此我们只需考察以“）”的字符，状态转移方程如下图所示。注意dp的边界条件，图中并没有体现出来。
class Solution:
def longestValidParentheses(self, s: str) -> int:
n = len(s)
dp = [0] * n
res = 0
for i in range(1, n):
if s[i] == ')':
if s[i - 1] == '(' and i - 2 >= 0:
dp[i] = dp[i - 2] + 2
elif i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == '(': # s[i - 1] == ')'
if i - dp[i - 1] - 2 >= 0:
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
else:
dp[i] = dp[i - 1] + 2
res = max(res, dp[i])
return res
四、删除无效的括号
此题为leetcode第301题
思路：可以使用DFS和BFS两种方式。（1）DFS，首先需要知道要删除几个左括号和右括号，分别记为cntleft和cntright，挨个遍历，除了能配对的，统计剩下的左右括号个数。然后在原始字符串上面进行删除操作，遍历删除的字符位置[0, len(s)-1], 对应字符为左右括号时，分别递归；当前删除位置需要传递给下一次递归，因为每次删除一个字符后，字符串长度是减少1的，而删除的位置正好是下一次迭代中开始删除的首位。是在循环删除的时候，如果下一个字符和上一次回溯结束后的字符一样时，不需要再重复处理。当cntleft和cntright都为0时，检查字符串s是否有效。（2）BFS，从删除一个括号开始枚举，依次删除2个括号、3个括号等等，分别为level 1、level 2、level 3等等。如果有某一层能有一个及以上的字符串合法，那么所有合法的字符串即为答案，不用在继续下去，因为已经满足了“删除最小数量的括号”的要求。
# DFS
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
# 确定有几个多余的括号
cntleft, cntright = 0, 0
for c in s:
if c == '(':
cntleft += 1
if cntleft > 0 and c == ')':
cntleft -= 1
elif cntleft == 0 and c == ')':
cntright += 1
self.res = []
self.dfs(s, 0, cntleft, cntright)
return self.res
def is_valid(self, s):
count = 0
for c in s:
if c == '(':
count += 1
if c == ')':
count -= 1
if count < 0:
return False
return count == 0
def dfs(self, s, start, cntleft, cntright):
if cntleft == 0 and cntright == 0 and self.is_valid(s):
self.res.append(s)
for i in range(start, len(s)):
# 如果相邻的两个字符相同，那么只删除一个就行
if i > start and s[i] == s[i - 1]:
continue
if s[i] == '(' and cntleft > 0:
self.dfs(s[:i] + s[i+1:], i, cntleft - 1, cntright)
if s[i] == ')' and cntright > 0:
self.dfs(s[:i] + s[i+1:], i, cntleft, cntright - 1)
# BFS
class Solution:
def removeInvalidParentheses(self, s: str) -> List[str]:
# 判断括号是否合法
def is_valid(s):
count = 0
for c in s:
if c == '(':
count += 1
if c == ')':
count -= 1
if count < 0:
return False
return count == 0
# BFS
level = {s}
while True:
valid_level = list(filter(is_valid, level)) # 将level里合法的字符串筛选出来
if valid_level: # 如果level不为空则找到了结果
return valid_level
# 挨个进入下一层
next_level = set() # 用set是为了去重
for item in level:
for i in range(len(item)):
if item[i] in '()': # 如果是括号就去掉
next_level.add(item[:i] + item[i + 1:])
level = next_level
本文摘自 ：https://blog.51cto.com/u
