1. 问题背景与核心挑战
"删除无效的括号"是LeetCode上的一道经典难题(编号301),要求从给定字符串中移除最少数量的无效括号,使剩余字符串成为有效的括号组合。这道题在2024年各大科技公司的面试中出现频率极高,尤其是考察候选人对DFS/BFS的应用能力。
问题的难点在于如何高效处理两种无效情况:
- 多余的左括号(如"(a(b)")
- 多余的右括号(如")a)b(")
常规的暴力解法需要检查所有可能的子串组合,时间复杂度高达O(2^n)。我在实际面试中遇到过有候选人尝试用正则表达式解决,结果陷入了无限回溯的陷阱。正确的解法需要结合以下核心技术点:
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 解法思路与算法选择
2.1 BFS层序遍历法
BFS是这道题最直观的解法,其核心思想是通过层级遍历逐步删除字符,直到找到有效字符串为止。具体实现步骤:
python复制from collections import deque
def removeInvalidParentheses(s):
def is_valid(s):
count = 0
for char in s:
if char == '(':
count += 1
elif char == ')':
count -= 1
if count < 0:
return False
return count == 0
queue = deque([s])
visited = set([s])
result = []
found = False
while queue:
current = queue.popleft()
if is_valid(current):
result.append(current)
found = True
if found:
continue
