LeetCode 301 删除无效的括号：python3 题解
题目链接：301. 删除无效的括号目录
[*]1. 题目含义与核心目标
[*]2. 解题思路分析
[*]思路一：广度优先搜索 (BFS) —— 最直观
[*]思路二：深度优先搜索 (DFS) + 回溯 —— 更高效
[*]3. 代码实现
[*]4. 复杂度分析
[*]5. 总结与建议
1. 题目含义与核心目标
题目描述：
给定一个字符串 s，其中包含小写字母和括号 ( 和 )。我们需要删除最小数量的括号，使得剩下的字符串中括号是有效的。返回所有可能的结果。
什么是“有效括号”？
[*]左括号 ( 必须有对应的右括号 ) 闭合。
[*]闭合顺序必须正确，不能出现 )( 这种情况。
[*]字母不影响括号的有效性，可以保留。
核心难点：
[*]最小数量：我们不能随便删，必须保证删得最少。这意味着如果删 1 个括号能变有效，就不能删 2 个。
[*]所有可能：可能有多种删除方案都能达到“最小删除数”且结果有效，需要全部找出。
[*]去重：不同的删除位置可能产生相同的字符串（例如 (()，删除第 1 个或第 2 个 ( 结果都是 ()），结果列表中不能有重复。
2. 解题思路分析
这道题主要有两种经典的解法：广度优先搜索 (BFS) 和 深度优先搜索 (DFS/回溯)。
思路一：广度优先搜索 (BFS) —— 最直观
逻辑：
想象我们处于第 0 层（原字符串）。
[*]检查当前层的字符串是否有效。如果有效，因为它们是目前删除最少的（层数最低），直接收集所有有效结果并返回。
[*]如果当前层没有有效字符串，我们就生成下一层。下一层的所有字符串，都是由当前层字符串各删除一个字符得到的。
[*]重复上述过程，直到找到有效字符串为止。
优点：
[*]天然保证“删除数量最小”。因为 BFS 是按层遍历的，第一层是删 0 个，第二层是删 1 个……第一次遇到有效解的层数，必然是删除最少的。
缺点：
[*]可能会生成大量重复字符串，需要使用 visited 集合去重。
[*]空间消耗较大，因为需要存储每一层的所有状态。
思路二：深度优先搜索 (DFS) + 回溯 —— 更高效
逻辑：
[*]预计算：先扫描一遍字符串，计算出最少需要删除多少个左括号 (left_remove) 和多少个右括号 (right_remove) 才能可能变有效。
[*]例如：) (，需要删 1 个 ) 和 1 个 (。
[*]回溯删除：使用递归，尝试删除指定数量的括号。
[*]剪枝与去重：
[*]如果剩余需要删除的数量小于 0，剪枝。
[*]如果当前括号匹配状态不合法（右括号多于左括号），剪枝。
[*]关键去重：如果连续出现相同的括号（如 ))），删除第一个和删除第二个结果是一样的。我们规定只删除连续相同括号中的第一个，跳过后续的，避免重复计算。
优点：
[*]效率通常比 BFS 高，因为我们有明确的删除目标数量，不需要盲目尝试。
[*]空间消耗相对较小。
3. 代码实现
下面提供 BFS 解法的完整代码。为了代码的自包含性，我添加了必要的导入和详细的注释。
from typing import List
from collections import deque
class Solution:
def removeInvalidParentheses(self, s: str) -> List:
"""
BFS 解法：
层层递进，第一层是原字符串，第二层是删 1 个字符的所有可能，第三层是删 2 个...
一旦在某一层发现有效字符串，该层所有有效字符串即为答案（保证删除最少）。
"""
# 辅助函数：判断字符串括号是否有效
def isValid(string: str) -> bool:
count = 0
for char in string:
if char == '(':
count += 1
elif char == ')':
count -= 1
# 如果右括号多于左括号，直接无效
if count < 0:
return False
# 最后左括号必须全部闭合
return count == 0
# 队列用于 BFS，初始放入原字符串
queue = deque()
# 集合用于记录访问过的字符串，防止重复处理（关键优化）
visited = set()
# 存储最终结果
result = []
# 标记是否已经找到了有效解。一旦找到，当前层处理完后就停止，不再深入下一层
found = False
while queue:
# 当前层的节点数量
level_size = len(queue)
# 遍历当前层的所有字符串
for _ in range(level_size):
curr_s = queue.popleft()
# 1. 检查当前字符串是否有效
if isValid(curr_s):
result.append(curr_s)
found = True
# 2. 如果本层已经找到了有效解，我们就不再生成下一层（删除更多字符）了
# 因为题目要求删除最小数量，本层就是最小数量
if found:
continue
# 3. 如果还没找到有效解，生成下一层状态（尝试删除每一个字符）
for i in range(len(curr_s)):
# 跳过非括号字符，因为题目只让删括号（其实删字母也能变有效，但删括号更优，且题目隐含意图是修括号）
# 严格来说，删字母不会改善括号匹配，所以只尝试删括号可以优化，但全删也能过
# 这里为了逻辑通用，尝试删除任意位置字符
if curr_s not in ('(', ')'):
continue
# 生成新字符串：删除索引 i 处的字符
next_s = curr_s[:i] + curr_s
# 如果这个新字符串没被访问过，加入队列
if next_s not in visited:
visited.add(next_s)
queue.append(next_s)
# 如果本层找到了有效解，直接返回，不再处理下一层
if found:
return result
# 如果一直没找到（理论上不会，因为全删完是空串，空串有效），返回空列表或 [""]
return result if result else [""]4. 复杂度分析
假设字符串长度为 \(N\)。
BFS 解法：
[*]时间复杂度: \(O(2^N)\)。最坏情况下，每个字符都有删或不删两种选择。虽然有 visited 去重，但状态空间依然很大。
[*]空间复杂度: \(O(2^N)\)。队列和 visited 集合可能存储大量中间字符串。
DFS 解法：
[*]时间复杂度: \(O(2^N)\)。理论上也是指数级，但因为我们要删除的括号数量通常远小于 \(N\)，且有剪枝（open_cnt < 0 时停止）和去重（连续括号只删第一个），实际运行速度远快于 BFS。
[*]空间复杂度: \(O(N)\)。主要是递归栈的深度和存储结果的空间。
5. 总结与建议
[*]理解题意：核心是“最小删除”和“所有结果”。
[*]选择方法：
[*]如果是面试，DFS 解法 更受青睐，因为它展示了你对剪枝、回溯和去重的掌握，且效率更高。
[*]如果是为了快速理解“最小步数”，BFS 解法 的逻辑更直观（层序遍历即步数）。
[*]关键点：
[*]去重：处理连续相同括号（如 ((）时，避免重复计算。
[*]剪枝：在构建字符串过程中，一旦发现右括号多于左括号，立即停止该分支。
[*]预计算：先算出要删几个，比盲目尝试要快得多。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]