Python：字符串字符替换生成所有组合的高效实现方案

给定字典 d = {'R': ['a', 'g'], 'Y': ['c', 't']} 和字符串 s = '----YY----RR----'，需要将字符串中的每个占位符（如Y、R）替换为字典中对应列表的字符，生成所有可能的组合输出。原实现通过多层嵌套循环+字符串替换+集合去重的方式，效率极低，尤其是当占位符或可选字符数量增加时，性能会急剧下降。

原代码的核心问题 #

• 多层嵌套循环导致时间复杂度指数级增长，且存在大量重复遍历字典的冗余操作
• 多次调用str.replace()每次仅替换一个字符，效率低下
• 使用集合去完全多余，合理生成的组合本身就是唯一的

高效实现方案 #

利用itertools.product生成笛卡尔积（Python标准库底层用C实现，远快于手动嵌套循环），具体步骤如下：

1. 统计原字符串中每个占位符的出现次数
2. 对每个占位符，生成其对应字符列表的n次笛卡尔积（n为该占位符的出现次数），并将每个元组拼接为字符串（比如Y出现2次，生成['cc', 'ct', 'tc', 'tt']）
3. 将所有占位符的替换候选组合再做一次笛卡尔积，得到所有可能的替换组合
4. 对每个替换组合，批量替换原字符串中的占位符，得到最终结果

代码实现

import itertools
from collections import Counter

d = {'R': ['a', 'g'], 'Y': ['c', 't']}
s = '----YY----RR----'

# 统计每个占位符在原字符串中的出现次数
placeholder_counts = Counter(c for c in s if c in d)

# 生成每个占位符对应的替换候选列表
replace_candidates = {}
for placeholder, chars in d.items():
    count = placeholder_counts[placeholder]
    # 生成count次笛卡尔积并拼接为字符串
    candidates = [''.join(combo) for combo in itertools.product(chars, repeat=count)]
    replace_candidates[placeholder] = candidates

# 生成所有占位符候选的笛卡尔积组合
all_combinations = itertools.product(*replace_candidates.values())

# 遍历组合并替换输出
for combo in all_combinations:
    result = s
    for placeholder, replacement in zip(replace_candidates.keys(), combo):
        result = result.replace(placeholder, replacement)
    print(result)

方案优势 #

• 效率更高：itertools.product直接生成所有组合，避免手动嵌套循环的冗余操作
• 替换更高效：每个占位符仅需替换一次（比如一次性把所有Y替换成cc），而非逐个替换
• 无需去重：生成的组合天然唯一，省去集合去重的额外开销
• 扩展性强：无论字典中有多少占位符、每个占位符对应多少可选字符，代码都能自动适配，无需修改循环结构

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