#VO辅助 #VO代面 #VO助攻 #Google #删除括号 #BFS

Google 面试经验分享：删除括号使字符串合法 BFS题 - Oavoservice

2025-05-22

Google 0522 面经

Candidate 在 Google coding 环节遇到了经典题 —— 删除括号使字符串合法。

今天面试官是一个资深工程师，看起来比较专业，先是双方自我介绍，然后直接就是 Coding，上来就出一道经典的字符串处理题。

题目描述

通过删除最少数量的括号，使给定的括号字符串合法。返回所有可能的合法字符串。

解题思路

这是一道经典的BFS 字符串处理问题，关键在于逐层删除括号：

BFS 搜索：从原字符串开始，逐层删除括号
合法性检查：检查每个字符串是否合法
去重处理：避免重复处理相同的字符串
最优解：一旦找到合法字符串，该层就是最优解

代码实现

from collections import deque

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

def remove_invalid_parentheses(s):
    """删除最少数量的括号使字符串合法"""
    if not s:
        return [""]
    
    # BFS 搜索
    queue = deque([s])
    visited = {s}
    result = []
    found = False
    
    while queue:
        level_size = len(queue)
        
        for _ in range(level_size):
            current = queue.popleft()
            
            # 检查当前字符串是否合法
            if is_valid(current):
                result.append(current)
                found = True
            
            # 如果已经找到合法字符串，不再继续删除
            if found:
                continue
            
            # 尝试删除每个括号
            for i in range(len(current)):
                if current[i] in '()':
                    # 跳过重复的括号
                    if i > 0 and current[i] == current[i-1]:
                        continue
                    
                    # 生成新字符串
                    new_string = current[:i] + current[i+1:]
                    
                    if new_string not in visited:
                        visited.add(new_string)
                        queue.append(new_string)
        
        # 如果找到合法字符串，返回结果
        if found:
            break
    
    return result if result else [""]

算法分析

时间复杂度：O(2^n) - 最坏情况下需要尝试所有可能的删除组合
空间复杂度：O(2^n) - 存储所有可能的字符串
核心思想：BFS 逐层删除，一旦找到合法字符串就停止

优化版本

可以通过预处理减少搜索空间：

def remove_invalid_parentheses_optimized(s):
    """优化版本：预处理确定需要删除的括号数量"""
    # 计算需要删除的左括号和右括号数量
    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
    
    result = []
    
    def backtrack(string, index, left_count, right_count, left_rem, right_rem, path):
        if index == len(string):
            if left_rem == 0 and right_rem == 0 and is_valid(path):
                result.append(path)
            return
        
        char = string[index]
        
        # 跳过当前字符
        if char == '(' and left_rem > 0:
            backtrack(string, index + 1, left_count, right_count, left_rem - 1, right_rem, path)
        elif char == ')' and right_rem > 0:
            backtrack(string, index + 1, left_count, right_count, left_rem, right_rem - 1, path)
        
        # 保留当前字符
        path += char
        if char != '(' and char != ')':
            backtrack(string, index + 1, left_count, right_count, left_rem, right_rem, path)
        elif char == '(':
            backtrack(string, index + 1, left_count + 1, right_count, left_rem, right_rem, path)
        elif char == ')' and left_count > right_count:
            backtrack(string, index + 1, left_count, right_count + 1, left_rem, right_rem, path)
        path = path[:-1]  # 回溯
    
    backtrack(s, 0, 0, 0, left_removed, right_removed, "")
    return result if result else [""]

测试用例

# 测试代码
test_cases = [
    "()())()",
    "(a)())()",
    ")(",
    "(((",
    "()"
]

for test in test_cases:
    result = remove_invalid_parentheses(test)
    print(f"输入: {test}")
    print(f"输出: {result}")
    print()

面试官看完直接点头："Great solution! The BFS approach is very efficient."

Candidate 成功拿下这一轮。

这就是 OAVOSERVICE 实时 VO 辅助的威力：

不是死记硬背题库，而是帮你在最关键的时刻，快速理清思路，稳定发挥，稳稳过关！

面试技巧分享

在 Google 的面试中，除了算法实现，面试官还会关注：

1. 算法选择

能够快速识别出这是一道 BFS 问题，并选择合适的搜索策略。

2. 优化思路

能够提供多种解决方案，包括基础版本和优化版本。

3. 边界条件处理

考虑各种边界情况，如空字符串、全括号、无括号等。

4. 代码质量

写出清晰、高效的代码，注意去重和剪枝优化。

Oavoservice 实时辅助服务

在这次 Google 面试中，我们的实时辅助系统发挥了关键作用：

快速思路提示：在候选人卡壳时，立即提供 BFS 搜索的核心思路
算法指导：推荐使用 BFS 来实现最优解搜索
代码优化：提供最优的代码实现，包括去重和剪枝
边界处理：帮助候选人考虑各种边界情况和异常处理

结语

删除括号使字符串合法虽然是一道经典题目，但在面试的紧张环境下，能够快速理清思路并正确实现并不容易。这就是为什么我们的实时辅助服务如此重要。

如果你正在准备 Google 或其他公司的技术面试，欢迎联系 Oavoservice。我们拥有丰富的面试经验和专业的辅助团队，能够在你最需要的时候提供及时有效的帮助。

Oavoservice - 让每一次面试都成为成功的机会！

需要辅助的同学随时dd哦，vo开始前支持mock！