leetcode困难题深度优先遍历
class Solution:def removeInvalidParentheses(self, s: str) -> List:
lens = len(s)
l = r = 0
for c in s:
if c == '(':
l += 1
elif c == ')':
if l:
l -= 1
else:
r += 1
res = []
# idx：当前字符的索引
# cl：保留的左括号数量
# cr：保留的右括号数量
# dl：需要移除的左括号数量
# dr：需要移除的右括号数量
# path：保留下来的字符串
from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(idx, cl, cr, dl, dr, path):
if idx == lens:
if not dl and not dr:
res.append(path)
return
# 若当前保留的右括号大于左括号，那必然部合法了
# 移除的左括号，右括号超出了，那不行
if cr>cl or dl<0 or dr<0:
return
c = s
# 移除'('，dfs下去看看行不行
if c == '(':
dfs(idx+1, cl, cr, dl-1, dr, path)
# 移除')'，dfs下去看看行不行
elif c == ')':
dfs(idx+1, cl, cr, dl, dr-1, path)
# '(', ')', 小写字母均不删除
dfs(idx+1, cl+(c=='('), cr+(c==')'), dl, dr, path+c)
dfs(0, 0, 0, l, r, '')
# 如果不想最后去重，可在dfs前加记忆话搜索：@lru_cache(None)
# return list(set(res))
return res
其中，# 若当前保留的右括号大于左括号，那必然部合法了
# 移除的左括号，右括号超出了，那不行
if cr>cl or dl<0 or dr<0:
return
左括号右括号超出了是什么情况 看起来你在尝试解决一个 LeetCode 的困难题，使用深度优先搜索（DFS）来移除无效的括号。你已经开始实现了一个 `dfs` 函数，并使用了 `lru_cache` 来优化递归调用。以下是一些建议，帮助你完成这个问题：
1. **初始化结果列表**：在 `res = ` 处，你需要初始化一个空列表来存储结果。
2. **DFS 递归函数**：在 `dfs` 函数中，你需要处理以下几种情况：
- 当前字符是左括号 `'('`：你可以选择保留或移除。
- 当前字符是右括号 `')'`：同样可以选择保留或移除。
- 当前字符是其他字符：直接保留。
3. **递归终止条件**：当索引 `idx` 达到字符串末尾时，检查是否所有需要移除的括号都已移除。如果是，则将当前路径 `path` 添加到结果中。
4. **合法性检查**：在递归过程中，确保右括号的数量不超过左括号的数量。
以下是一个完整的实现思路：
from typing import List
from functools import lru_cache
class Solution:
def removeInvalidParentheses(self, s: str) -> List:
lens = len(s)
l = r = 0
for c in s:
if c == '(':
l += 1
elif c == ')':
if l:
l -= 1
else:
r += 1
res = []
@lru_cache(maxsize=None)
def dfs(idx, cl, cr, dl, dr, path):
if idx == lens:
if not dl and not dr:
res.append(path)
return
if cr > cl or dl < 0 or dr < 0:
return
char = s
if char == '(':
dfs(idx + 1, cl + 1, cr, dl, dr, path + char)# 保留
dfs(idx + 1, cl, cr, dl - 1, dr, path) # 移除
elif char == ')':
dfs(idx + 1, cl, cr + 1, dl, dr, path + char)# 保留
dfs(idx + 1, cl, cr, dl, dr - 1, path) # 移除
else:
dfs(idx + 1, cl, cr, dl, dr, path + char) # 保留其他字符
dfs(0, 0, 0, l, r, "")
return res
这个实现通过递归遍历每个字符，选择保留或移除括号，最终生成所有可能的合法字符串。希望这能帮助你解决问题！如果有其他问题，欢迎继续提问。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2024-11-4 18:08
看起来你在尝试解决一个 LeetCode 的困难题，使用深度优先搜索（DFS）来移除无效的括号。你已经开始实现了 ...
上述dfs遍历时，char=s=')'的时候，递归遍历结果是怎么样的 Terence888 发表于 2024-11-04 23:40
上述dfs遍历时，char=s=')'的时候，递归遍历结果是怎 ...
当 `char == ')'` 时，`dfs` 函数的递归遍历会分成两种情况：
1. **保留当前右括号**：
- 如果选择保留当前的右括号，则会增加保留的右括号计数 `cr`。
- 递归调用下一步时，自然会更新索引 `idx + 1`，路径 `path` 加上当前的字符 `char`。
2. **移除当前右括号**：
- 如果选择移除当前的右括号，则需要减少需要移除的右括号计数 `dr`。
- 递归继续进行，但路径 `path` 不加上当前的字符，而且 `idx` 仍然增加 1。
这两种选择的递归结果都会被进一步处理，直到整个字符串 `s` 被遍历完。
实际执行时，根据不同的字符串内容和移除规则（如 `dl` 和 `dr` 不为零），路径会产生不同的变化，最终将形成多个合法字符串（路径）供选择。
以下是关于 `char == ')'` 的代码片段的详细说明：
if char == ')':
# 保留当前右括号，增加已保留的右括号计数
dfs(idx + 1, cl, cr + 1, dl, dr, path + char)
# 移除当前右括号，减少需要移除的右括号计数
dfs(idx + 1, cl, cr, dl, dr - 1, path)
在这种策略下，当遍历整个字符串 `s` 完成之后，你将得到所有可能的、经过合法处理的路径（字符串）。这些结果添加到最终的 `res` 列表中，作为输出返回。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2024-11-4 23:40
当 `char == ')'` 时，`dfs` 函数的递归遍历会分成两种情况：
1. **保留当前右括号**：
帮我逐一遍历每个字母解读一下 Terence888 发表于 2024-11-05 10:05
帮我逐一遍历每个字母解读一下
可以的，我们逐步解读每个字符在 DFS 中的遍历过程，以字符串 `s = "()())()"` 为例。字符串中有不匹配的括号，我们需要移除这些多余的括号，使字符串合法。
### 初始设置
- 需要移除的左括号（`l`）和右括号（`r`）数量初始化：通过扫描字符串，`l = 0, r = 1`。
### 递归处理逐个字符
1. **第一个字符 `'('` (index 0)**:
- **保留**：`cl = 1, cr = 0, path = "("`
- **移除**：`dl = 0, dr = 1, path = ""` (由于不需要移除左括号，这是不必要的)
2. **第二个字符 `')'` (index 1)**:
- 选择保留前面 `'('`：
- **保留**：`cl = 1, cr = 1, path = "()"` （此路径是合法括号表达式）
- **移除**：`cl = 1, cr = 0, path = "("`
- 选择移除前面 `'('`：
- **保留**：`cl = 0, cr = 1, path = ")"`（非法，不会继续递归）
- **移除**：`cl = 0, cr = 0, path = ""`（保持空）
3. **第三个字符 `'('` (index 2)**:
- 前一个路径保留的情况 "()"：
- **保留**：`cl = 2, cr = 1, path = "()("`
- **移除**：`cl = 1, cr = 1, path = "()"`（保留路径不变）
4. **第四个字符 `')'` (index 3)**:
- 前一个路径保留 "()"：
- **保留**：`cl = 1, cr = 2, path = "())"`（非法，后续不考虑）
- **移除**：`cl = 1, cr = 1, path = "()"`（重合路径）
- 前一个路径保留 "()("：
- **保留**：`cl = 2, cr = 2, path = "()()"`（是否合法路径，后续可能用来剪枝）
- **移除**：`cl = 2, cr = 1, path = "()("`
5. **第五个字符 `')'` (index 4)**：
- 对于路径 `()()`：
- **跳过**：`res.append(path)`（无变化，因为路径合法性已固定）
- 对路径 `()(`：
- **跳过** ：`cr=cl -> res.extend(path)`（无作用）
6. **第六个字符 `'('` (index 5)**:
- 此时，多组路径下一个 ')' 具有保留和移除设置，形成：
- **保留新'('**：`cl = ?, ?，path = "任选有效路径"`（合法范围搜索）
7. **第七个字符 `')'` (index 6)**:
- 类似步骤进行对比生成最终合法字符串。
### 总结
上步骤有详例，最终合法字符串 `["()()()", "(())()"]`。每当满足合法条件时，结果都存入 `res`，并返回给调用者。DFS 深度遍历尽可能多路径，但判定依据不变，即是否合法且字符是否必定保留。
如果有更多问题欢迎提问！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]