加拿大Zoom面试算法题LeetCode 301 Python解法攻略 
最近参加了加拿大公司的Zoom面试，遇到了一道LeetCode 301的算法题，分享一下我的Python解法思路！希望能帮助到正在准备面试的小伙伴们~ 
题目回顾：Remove Invalid Parentheses (LeetCode 301)
给定一个包含括号和其他字符的字符串，移除最少数量的无效括号，使字符串有效。返回所有可能的结果。
示例输入:
"()())()"
示例输出:
Python解法思路 
BFS广度优先搜索解法
from collections import deque
def removeInvalidParentheses(s):
def is_valid(string):
count = 0
for char in string:
if char == '(':
count += 1
elif char == ')':
count -= 1
if count < 0:
return False
return count == 0
queue = deque()
visited = set()
result = []
found = False
while queue:
current = queue.popleft()
if is_valid(current):
result.append(current)
found = True
if found:
continue
for i in range(len(current)):
if current not in '()':
continue
new_str = current + current
if new_str not in visited:
visited.add(new_str)
queue.append(new_str)
return result if result else
优化解法：DFS + 剪枝 
def removeInvalidParentheses(s):
result = []
left_removed = 0
right_removed = 0
# 第一步：计算需要移除的左右括号数量
for char in s:
if char == '(':
left_removed += 1
elif char == ')':
if left_removed > 0:
left_removed -= 1
else:
right_removed += 1
def dfs(index, left_count, right_count, left_rem, right_rem, path):
if index == len(s):
if left_rem == 0 and right_rem == 0:
result.append("".join(path))
return
char = s
# 情况1：跳过当前字符（如果是括号且需要移除）
if (char == '(' and left_rem > 0) or (char == ')' and right_rem > 0):
dfs(index + 1,
left_count,
right_count,
left_rem - (1 if char == '(' else 0),
right_rem - (1 if char == ')' else 0),
path)
# 情况2：保留当前字符
path.append(char)
if char not in '()':
dfs(index + 1, left_count, right_count, left_rem, right_rem, path)
elif char == '(':
dfs(index + 1, left_count + 1, right_count, left_rem, right_rem, path)
elif char == ')' and left_count > right_count:
dfs(index + 1, left_count, right_count + 1, left_rem, right_rem, path)
path.pop()
dfs(0, 0, 0, left_removed, right_removed, [])
return list(set(result)) if result else
面试小贴士 
- 先和面试官确认输入输出要求
- 从暴力解法开始，逐步优化
- 注意时间复杂度和空间复杂度的分析
- 多写测试用例验证边界条件
祝大家面试顺利！拿下加拿大offer！
有问题欢迎在评论区讨论~
BFS解法优劣势
DFS+剪枝解法优劣势
DFS解法效率高
。于是我切换到DFS+剪枝的优化版本，这也是加拿大面试官常期待的——不仅要能写代码，还要能优化！我特别强调了如何预计算需要移除的左右括号数量，从而减少不必要的递归分支。
，优雅のAC~
”
"