求Python无库实现的含?通配符01字符串状态枚举算法

核心思路 #

问题本质是对字符串中的每个?进行0/1分支遍历，无需依赖任何第三方库，可通过两种高效方式实现：

• 迭代扩展：通过逐步更新结果列表，避免递归深度限制，适配超长字符串场景
• 递归生成器：代码简洁直观，按需生成结果，内存占用更低

迭代实现（无递归深度限制） #

从空字符串开始，逐个处理输入字符：遇到?就将现有所有结果分别追加0和1，遇到0/1则直接追加，最终得到所有可能状态：

def generate_all_states(s):
    states = ['']
    for char in s:
        temp = []
        for state in states:
            if char == '?':
                temp.append(state + '0')
                temp.append(state + '1')
            else:
                temp.append(state + char)
        states = temp
    return states

# 测试示例
input_str = '1?01?1'
for result in generate_all_states(input_str):
    print(result)

生成器递归实现（低内存占用） #

用递归生成器逐个字符处理，遇到?时分叉生成两种结果，适合不需要一次性保存所有结果的场景：

def generate_all_states(s):
    if not s:
        yield ''
        return
    first = s[0]
    for rest in generate_all_states(s[1:]):
        if first == '?':
            yield '0' + rest
            yield '1' + rest
        else:
            yield first + rest

# 测试示例
input_str = '1?01?1'
for result in generate_all_states(input_str):
    print(result)

示例输出（输入1?01?1） #

110111
110101
100111
100101

内容的提问来源于stack exchange，提问作者root