1. 问题背景与核心挑战
这道LeetCode难题编号为301,题目要求我们从一个包含左右括号和其他字符的字符串中,删除最少数量的无效括号,使得剩余的字符串成为有效的括号组合。所谓有效括号,需要满足每个左括号都能找到对应的右括号,并且整体嵌套顺序正确。
初次看到这个问题时,很多人的第一反应可能是用栈结构来判断括号有效性。但这里有个关键区别:常规的括号验证是判断给定字符串是否有效,而本题需要生成所有可能的有效组合。这种从判断性到生成性的转变,使得问题复杂度呈指数级上升。
在实际面试场景中,这道题经常出现在谷歌、Facebook等大厂的中高级算法面试环节。它不仅考察候选人对DFS/BFS等基础算法的掌握程度,更能检验对剪枝优化和去重处理等高级技巧的应用能力。根据我的面试官经验,约70%的候选人在首次遇到这个问题时都无法给出最优解法。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 解法思路分析与选择
2.1 暴力搜索法的局限性
最直观的解法是枚举所有可能的子字符串,然后检查每个子串的有效性。对于一个长度为n的字符串,子字符串总数是2^n量级。即使通过提前计算需要删除的左右括号数量进行过滤,这种方法的复杂度仍然难以接受。以20个字符的输入为例,可能需要处理百万级别的候选串。
2.2 BFS层序遍历方案
广度优先搜索(BFS)在这里展现出独特优势。我们可以将问题转化为:通过逐层删除字符,寻找最早出现有效括号的层级。具体实现时:
- 将原始字符串放入队列
- 每次从队列取出一个字符串,检查有效性
- 如果无效,生成所有可能删除一个括号的新字符串加入队列
- 使用哈希集合进行去重
这种方法的优点是能找到最短的删除步数,但空间消耗较大,最坏情况下需要存储O(n^k)个中间状态(k为需要删除的括号数)。
2.3 DFS回溯+剪枝优化
深度优先搜索配合剪枝往往能获得更好的实际性能。核心思路是:
- 先扫描字符串,计算需要删除的多余左括号数left_remove和右括号数right_remove
- 使用回溯法尝试删除字符,在递归过程中维护当前左括号比右括号多的数量balance
- 当balance为负时立即剪枝
- 最终balance为0且删除数量等于预计算值时保存结果
这种方法通过提前计算删除数量和实时平衡检测,能有效减少搜索空间。在我的性能
