题目重点：对每个 * 做 0/1 分支，说明结果数 2^k 与空串、连续通配符及去重边界。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版输入仅含 0、1、*，每个 * 独立替换为一位；按左到右 0 分支再 1 分支输出。
- 不同替换选择得到不同长度相同的字符串，通常无需去重；非法字符直接报错。
解题路线
- 维护部分结果列表，扫描固定字符时在每个前缀后附该字符；遇 * 时把每个前缀复制为加 0 和加 1 两条。
- 或用 DFS(path,index) 递归分叉，输出可流式 yield；若结果很多，显式列表会耗指数空间。
- k 个星号产生 2^k 条，每条长度 n；计算复杂度时必须包含结果复制成本。
手动走一遍
01*01* 依序生成 010010、010011、011010、011011。空输入只有一个结果：空串。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def expand_bits(pattern):
"""Replace each * with 0 or 1, in left-to-right binary choice order."""
result = [""]
for char in pattern:
if char == "*":
result = [prefix + bit for prefix in result for bit in "01"]
elif char in "01":
result = [prefix + char for prefix in result]
else:
raise ValueError("pattern must contain only 0, 1, *")
return result
复杂度
k 个通配符时输出有 2^k 个长度 n 的字符串，时间与输出空间 O(n·2^k)；流式 DFS 工作栈 O(n) 但总输出仍指数。
易错点与追问
容易失分的边界
- 只生成一条替换。
- 多个 * 被错误地绑定为相同 bit。
- 忘记空输入的一个空结果。
- 声称可显式输出所有结果仍只占 O(n) 总空间。
继续深挖
- 只要第 m 个结果能否直接计算？
- 只统计结果数量如何防整数溢出？
- 如果 * 可匹配空串或多位会怎样？
