题目描述
实现一个函数，输入一个可能包含通配符 ? 的二进制字符串，输出所有可能的二进制字符串组合。通配符 ? 可以被替换为 0 或 1。
示例
输入: "01?0"
输出: ["0100", "0110"]
输入: "01??"
输出: ["0100", "0101", "0110", "0111"]
输入: "0?1?"
输出: ["0010", "0011", "0110", "0111"]
解题思路
这是一道经典的回溯/DFS 题目：
- 遇到
0或1时直接保留 - 遇到
?时分叉，分别尝试替换为0和1
如果有 k 个通配符，最终会产生 2^k 个结果。
Python 实现（回溯）
def generate_binary_strings(s: str) -> list:
result = []
def backtrack(index: int, current: list):
if index == len(s):
result.append(''.join(current))
return
if s[index] == '?':
# 分叉：尝试 0 和 1
current.append('0')
backtrack(index + 1, current)
current.pop()
current.append('1')
backtrack(index + 1, current)
current.pop()
else:
# 保留原字符
current.append(s[index])
backtrack(index + 1, current)
current.pop()
backtrack(0, [])
return result
迭代解法
def generate_binary_strings_iterative(s: str) -> list:
result = ['']
for char in s:
if char == '?':
# 每个现有结果都分裂成两个
result = [r + '0' for r in result] + [r + '1' for r in result]
else:
# 每个现有结果追加当前字符
result = [r + char for r in result]
return result
使用 itertools 的简洁解法
from itertools import product
def generate_binary_strings_itertools(s: str) -> list:
# 找到所有通配符位置
wildcards = [i for i, c in enumerate(s) if c == '?']
if not wildcards:
return [s]
result = []
# 生成所有 0/1 组合
for combo in product('01', repeat=len(wildcards)):
chars = list(s)
for i, c in zip(wildcards, combo):
chars[i] = c
result.append(''.join(chars))
return result
复杂度分析
- 时间复杂度：O(n × 2^k)，n 是字符串长度，k 是通配符数量
- 空间复杂度：O(n × 2^k) 存储所有结果
变体题目
面试官可能会追问：
- 如果通配符可以是任意字符 a-z？ 修改分叉逻辑，26 路分叉
- 如果只需要统计数量？ 直接返回 2^k，不需要生成
- 如果结果太多，需要分批返回？ 使用生成器
# 生成器版本，内存友好
def generate_binary_strings_generator(s: str):
def backtrack(index: int, current: list):
if index == len(s):
yield ''.join(current)
return
if s[index] == '?':
current.append('0')
yield from backtrack(index + 1, current)
current.pop()
current.append('1')
yield from backtrack(index + 1, current)
current.pop()
else:
current.append(s[index])
yield from backtrack(index + 1, current)
current.pop()
return backtrack(0, [])
需要面试辅助服务？联系我们
- 📧 Email: [email protected]
- 📱 Phone: +86 17863968105
需要面试真题？ 立刻联系微信 Coding0201，获得真题。