企业官网建设流程全解析

题目描述：

给你一个由若干括号和字母组成的字符串s，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按任意顺序返回。

示例 1：

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

示例 2：

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

示例 3：

输入：s = ")("输出：[""]

解题思路：

方法一：DFS + 剪枝（最优，推荐）

思路：

第一步：统计需要删除的左右括号数量

用一次遍历模拟括号匹配：

• 遇到(时leftToRemove++

• 遇到)时，如果leftToRemove > 0则配对成功（leftToRemove--），否则这个)多余（rightToRemove++）

第二步：DFS 尝试删除

对每个括号字符，有两种选择：

• 保留：加入当前路径

• 删除：如果还有删除配额（leftToRemove > 0或rightToRemove > 0），则跳过

关键剪枝：

• 当前路径中右括号数量不能超过左括号（rightCount > leftCount时剪枝）

• 剩余字符数不足以完成所需删除时剪枝

• 相邻相同括号只删第一个，避免重复解

去重：用HashSet存储结果

代码实现：

class Solution { unordered_set<string> result; int leftToRemove, rightToRemove; string s; public: vector<string> removeInvalidParentheses(string _s) { s = _s; leftToRemove = rightToRemove = 0; // 第一步：统计多余的左右括号数量 for (char c : s) { if (c == '(') { leftToRemove++; } else if (c == ')') { if (leftToRemove > 0) { leftToRemove--; } else { rightToRemove++; } } } dfs(0, "", 0, 0); return vector<string>(result.begin(), result.end()); } void dfs(int index, string current, int leftCount, int rightCount) { // 剪枝：右括号多于左括号，无效 if (rightCount > leftCount) return; if (index == s.size()) { if (leftToRemove == 0 && rightToRemove == 0) { result.insert(current); } return; } char c = s[index]; if (c == '(') { // 选择1：保留 dfs(index + 1, current + c, leftCount + 1, rightCount); // 选择2：删除（如果有配额） if (leftToRemove > 0) { leftToRemove--; dfs(index + 1, current, leftCount, rightCount); leftToRemove++; } } else if (c == ')') { // 选择1：保留 dfs(index + 1, current + c, leftCount, rightCount + 1); // 选择2：删除（如果有配额） if (rightToRemove > 0) { rightToRemove--; dfs(index + 1, current, leftCount, rightCount); rightToRemove++; } } else { // 字母直接保留 dfs(index + 1, current + c, leftCount, rightCount); } } };

复杂度分析：

• 时间复杂度：O(2^P × n)，P 是括号总数（≤20），最坏情况遍历所有子集

• 空间复杂度：O(n)，递归栈深度

方法二：BFS 逐层删除

思路：

BFS 逐层删除一个括号，直到找到有效的字符串。因为 BFS 按层遍历，第一次找到的有效字符串就是删除数量最少的 。

• 用queue存储当前层的所有字符串

• 用visited集合去重

• 处理完一层后，如果找到了有效字符串，只收集这一层的所有结果，不再继续下一层

代码实现：

class Solution { public: vector<string> removeInvalidParentheses(string s) { vector<string> result; unordered_set<string> visited{s}; queue<string> q{{s}}; bool found = false; while (!q.empty()) { int size = q.size(); for (int i = 0; i < size; i++) { string cur = q.front(); q.pop(); if (isValid(cur)) { result.push_back(cur); found = true; } if (found) continue; // 已找到最短解，不再扩展 for (int j = 0; j < cur.size(); j++) { if (cur[j] != '(' && cur[j] != ')') continue; string next = cur.substr(0, j) + cur.substr(j + 1); if (visited.insert(next).second) { q.push(next); } } } if (found) break; } return result.empty() ? vector<string>{""} : result; } bool isValid(const string& s) { int count = 0; for (char c : s) { if (c == '(') count++; else if (c == ')') { if (--count < 0) return false; } } return count == 0; } };

复杂度分析：

• 时间复杂度：O(n × 2^P)，最坏情况枚举所有删除组合

• 空间复杂度：O(2^P × n)，队列和 visited 集合存储大量字符串

两种方法对比：

BFS 的问题：空间占用大，需要存储大量中间字符串 。DFS 通过统计删除数量直接剪枝，空间效率更高。

总结：