LeetCode 301. 删除无效的括号

字数 2308 2025-12-14 04:43:03

LeetCode 301. 删除无效的括号

题目描述
给你一个由若干括号和字母组成的字符串 s，你需要从中删除最少数量的无效括号（可以是左括号 '(' 或右括号 ')'），使得剩下的括号字符串是有效的。如果有多个有效结果，你可以返回任意一个。

注意：

有效的括号字符串应当满足：每个左括号必须有对应的右括号，且括号顺序正确。
字符串中除了括号外还可能包含字母（小写或大写），这些字母可以被视为普通字符，不需要删除。

示例：

输入：s = "()())()"，输出：["(())()","()()()"]
输入：s = "(a)())()"，输出：["(a())()","(a)()()"]
输入：s = ")("，输出：[""]

解题过程循序渐进讲解

第一步：理解问题核心
题目要求删除最少数量的无效括号，使得括号匹配有效。这意味着我们需要找到一个或多个字符串，它们：

是原字符串删除某些字符（只能是括号）后的子序列。
括号匹配是合法的。
删除的括号数量尽可能少。

由于需要列举所有可能的结果（或其中任意一个），我们可以考虑使用广度优先搜索（BFS） 来逐层尝试删除括号，确保找到的就是删除最少括号的解。

第二步：分析如何判断括号字符串是否有效
一个简单的判断方法：遍历字符串，维护一个计数器 count：

遇到 '('，count++。
遇到 ')'，count--。
如果中途 count < 0，说明右括号多了，无效。
最后 count == 0 才有效。

例如："()())"

遍历：'(' → count=1, ')' → count=0, '(' → count=1, ')' → count=0, ')' → count=-1 → 无效。

第三步：BFS 搜索思路
我们可以把原字符串看作初始节点。每一层表示删除一个括号（左或右）后得到的新字符串。逐层搜索：

从队列中取出一个字符串。
检查它是否有效，如果有效就加入结果集（说明我们找到了删除最少括号的有效字符串）。
如果当前层已经找到有效字符串，就不需要继续向下一层搜索（因为我们要的是删除最少的）。
否则，生成所有可能删除一个括号的新字符串，加入队列（注意去重）。

例如：s = "()())()"

第一层：原字符串 "()())()" 无效。
第二层：尝试删除一个括号，得到例如 "())())()"、"()()())"、"()()))" 等，检查每个是否有效。如果发现有效字符串如 "(())()" 或 "()()()"，就记录下来。

第四步：BFS 实现细节

使用队列进行 BFS，初始队列包含原字符串。
使用集合 visited 避免重复处理相同字符串。
在每一层开始时，记录当前队列大小，然后依次处理该层的所有字符串。
对于每个字符串：
- 如果有效，加入结果列表，并设置一个标志表示当前层已经找到有效结果（但还需要处理完当前层所有字符串，因为可能同一层有多个有效结果）。
- 如果无效，则生成所有可能删除一个括号的新字符串，如果未访问过则加入下一层队列。
如果当前层找到了有效结果，直接返回结果列表（因为已经是最少删除数量）。

第五步：生成新字符串的方法
对于当前字符串，遍历每个字符：

如果字符是括号（'(' 或 ')'），则删除它，形成新字符串。
注意跳过连续相同的括号，避免生成重复字符串（例如 "(()" 删除第一个 '(' 和第二个 '(' 结果相同，但位置不同）。可以通过判断：如果当前字符和上一个字符相同，则跳过（因为删除哪个都会得到相同字符串）。

第六步：示例推演（以 s = "()())()" 为例）

初始队列：["()())()"]，visited 包含它。
第一层：取出 "()())()"，检查有效？遍历计数：(→1, )→0, (→1, )→0, )→-1，无效。
- 生成下一层：删除每个括号试试。
  - 删第一个 '('：得到 ")())()"。
  - 删第二个 ')'：得到 "(()())"。
  - 删第三个 '('：得到 "())()"。
  - 删第四个 ')'：得到 "()()()"（有效！）。
  - 删第五个 ')'：得到 "()())("。
  - 删第六个 '('：得到 "()()))"。
  - 删第七个 ')'：得到 "()())("（重复）。
    将未访问的加入下一层队列。
第二层处理时，发现 "()()()" 有效，同时可能还有 "(())()" 也有效（从其他删除方式得到）。收集所有当前层有效字符串，返回结果 ["(())()","()()()"]。

第七步：边界情况

如果字符串本身有效，直接返回它。
如果字符串只包含字母没有括号，直接返回它。
注意空字符串的情况：如输入 ")("，删除两个括号后得到 ""，这是有效的。

第八步：复杂度分析

最坏情况下，字符串长度 n，每个位置都可能删除或不删除，但 BFS 会按删除数量逐层增加，一旦找到就停止。时间复杂度约为 O(2^n) 但在实际中由于提前剪枝和去重，会快很多。
空间复杂度主要是队列和 visited 集合存储的字符串数量。

总结
本题通过 BFS 逐层尝试删除括号，确保首先找到的解是删除最少的。关键点包括：有效括号的判断、BFS 层序处理、生成新字符串时的去重。通过这种方法，我们可以高效地找到所有可能的最优解。

LeetCode 301. 删除无效的括号题目描述给你一个由若干括号和字母组成的字符串 s ，你需要从中删除最少数量的无效括号（可以是左括号 '(' 或右括号 ')' ），使得剩下的括号字符串是有效的。如果有多个有效结果，你可以返回任意一个。注意：有效的括号字符串应当满足：每个左括号必须有对应的右括号，且括号顺序正确。字符串中除了括号外还可能包含字母（小写或大写），这些字母可以被视为普通字符，不需要删除。示例：输入： s = "()())()" ，输出： ["(())()","()()()"] 输入： s = "(a)())()" ，输出： ["(a())()","(a)()()"] 输入： s = ")(" ，输出： [""] 解题过程循序渐进讲解第一步：理解问题核心题目要求删除最少数量的无效括号，使得括号匹配有效。这意味着我们需要找到一个或多个字符串，它们：是原字符串删除某些字符（只能是括号）后的子序列。括号匹配是合法的。删除的括号数量尽可能少。由于需要列举所有可能的结果（或其中任意一个），我们可以考虑使用广度优先搜索（BFS）来逐层尝试删除括号，确保找到的就是删除最少括号的解。第二步：分析如何判断括号字符串是否有效一个简单的判断方法：遍历字符串，维护一个计数器 count ：遇到 '(' ， count++ 。遇到 ')' ， count-- 。如果中途 count < 0 ，说明右括号多了，无效。最后 count == 0 才有效。例如： "()())" 遍历： '(' → count=1, ')' → count=0, '(' → count=1, ')' → count=0, ')' → count=-1 → 无效。第三步：BFS 搜索思路我们可以把原字符串看作初始节点。每一层表示删除一个括号（左或右）后得到的新字符串。逐层搜索：从队列中取出一个字符串。检查它是否有效，如果有效就加入结果集（说明我们找到了删除最少括号的有效字符串）。如果当前层已经找到有效字符串，就不需要继续向下一层搜索（因为我们要的是删除最少的）。否则，生成所有可能删除一个括号的新字符串，加入队列（注意去重）。例如： s = "()())()" 第一层：原字符串 "()())()" 无效。第二层：尝试删除一个括号，得到例如 "())())()" 、 "()()())" 、 "()()))" 等，检查每个是否有效。如果发现有效字符串如 "(())()" 或 "()()()" ，就记录下来。第四步：BFS 实现细节使用队列进行 BFS，初始队列包含原字符串。使用集合 visited 避免重复处理相同字符串。在每一层开始时，记录当前队列大小，然后依次处理该层的所有字符串。对于每个字符串：如果有效，加入结果列表，并设置一个标志表示当前层已经找到有效结果（但还需要处理完当前层所有字符串，因为可能同一层有多个有效结果）。如果无效，则生成所有可能删除一个括号的新字符串，如果未访问过则加入下一层队列。如果当前层找到了有效结果，直接返回结果列表（因为已经是最少删除数量）。第五步：生成新字符串的方法对于当前字符串，遍历每个字符：如果字符是括号（ '(' 或 ')' ），则删除它，形成新字符串。注意跳过连续相同的括号，避免生成重复字符串（例如 "(()" 删除第一个 '(' 和第二个 '(' 结果相同，但位置不同）。可以通过判断：如果当前字符和上一个字符相同，则跳过（因为删除哪个都会得到相同字符串）。第六步：示例推演（以 s = "()())()" 为例）初始队列： ["()())()"] ，visited 包含它。第一层：取出 "()())()" ，检查有效？遍历计数： ( →1, ) →0, ( →1, ) →0, ) →-1，无效。生成下一层：删除每个括号试试。删第一个 '(' ：得到 ")())()" 。删第二个 ')' ：得到 "(()())" 。删第三个 '(' ：得到 "())()" 。删第四个 ')' ：得到 "()()()" （有效！）。删第五个 ')' ：得到 "()())(" 。删第六个 '(' ：得到 "()()))" 。删第七个 ')' ：得到 "()())(" （重复）。将未访问的加入下一层队列。第二层处理时，发现 "()()()" 有效，同时可能还有 "(())()" 也有效（从其他删除方式得到）。收集所有当前层有效字符串，返回结果 ["(())()","()()()"] 。第七步：边界情况如果字符串本身有效，直接返回它。如果字符串只包含字母没有括号，直接返回它。注意空字符串的情况：如输入 ")(" ，删除两个括号后得到 "" ，这是有效的。第八步：复杂度分析最坏情况下，字符串长度 n，每个位置都可能删除或不删除，但 BFS 会按删除数量逐层增加，一旦找到就停止。时间复杂度约为 O(2^n) 但在实际中由于提前剪枝和去重，会快很多。空间复杂度主要是队列和 visited 集合存储的字符串数量。总结本题通过 BFS 逐层尝试删除括号，确保首先找到的解是删除最少的。关键点包括：有效括号的判断、BFS 层序处理、生成新字符串时的去重。通过这种方法，我们可以高效地找到所有可能的最优解。