1. 问题背景与核心挑战
今天想和大家分享一道LeetCode上的经典难题——"删除无效的括号"(题目编号301)。这道题在各大科技公司的面试中出现频率很高,特别是考察候选人对DFS/BFS算法的掌握程度以及对边界条件的处理能力。我第一次遇到这个问题时,花了整整一个下午才理清思路,现在把完整的解题思路和优化过程整理出来。
这个问题的核心是:给定一个由括号和小写字母组成的字符串,我们需要删除最少数量的无效括号,使剩下的字符串有效。所谓有效括号字符串,需要满足两个条件:1) 所有左括号和右括号正确匹配;2) 每个右括号都有对应的左括号。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 解题思路分析
2.1 暴力解法与复杂度分析
最直观的想法是生成所有可能的子字符串,然后检查它们是否是有效的。对于一个长度为n的字符串,每个字符都有"保留"或"删除"两种选择,所以总共有2^n种可能的子字符串。对于每个子字符串,我们需要O(n)的时间来验证其有效性,因此总时间复杂度是O(n*2^n)。
这种方法在小规模输入时勉强可用,但当n>20时就完全不可行了。以n=20为例,2^20≈100万,再乘以20就是2000万次操作,这在LeetCode上肯定会超时。
2.2 优化思路:剪枝与提前终止
我们可以通过以下几个观察来优化算法:
-
我们可以预先计算出需要删除的最少左括号和右括号数量。遍历字符串时:
- 遇到'('时,left_need加1
- 遇到')'时,如果left_need>0则减1,否则right_need加1
-
在递归过程中,我们可以跟踪当前的括号平衡状态。如果出现balance<0的情况(即右括号多于左括号),就可以立即终止当前分支的探索。
-
对于连续的相同括号,我们只需要考虑删除其中一个,避免生成重复的结果。
3. Python实现详解
3.1 预处理与初始化
python复制def removeInvalidParentheses(s):
# 计算需要删除的最少左右括号数
left_remove = right_remove = 0
for char in s:
if char == '(':
left_remove += 1
elif
