如何替换字符串中的#为指定字符集并生成所有组合？求算法及Python代码

核心思路 #

• 先定位原字符串中所有'#'的位置，假设共有n个'#'，每个'#'可独立选择字符集中的任意元素替换
• 生成字符集的n次笛卡尔积，每一组笛卡尔积结果对应一组替换方案
• 按顺序将每组替换方案的元素填入对应'#'位置，生成最终字符串

可运行Python代码 #

内置库实现版本（性能更高） #

import itertools
from typing import List, Union

def generate_all_combinations(s: str, char_set: Union[set, List]) -> List[str]:
    # 收集所有#的索引位置
    hash_indices = [i for i, c in enumerate(s) if c == '#']
    hash_count = len(hash_indices)
    # 无#场景直接返回原字符串
    if hash_count == 0:
        return [s]
    # 字符集元素统一转字符串，避免数字类型拼接报错
    char_list = [str(c) for c in char_set]
    # 生成n次笛卡尔积作为替换方案
    replace_plans = itertools.product(char_list, repeat=hash_count)
    # 按方案替换生成所有结果
    result = []
    s_list = list(s)
    for plan in replace_plans:
        for idx, pos in enumerate(hash_indices):
            s_list[pos] = plan[idx]
        result.append(''.join(s_list))
    return result

递归实现版本（无第三方依赖） #

from typing import List, Union

def generate_all_combinations_recursive(s: str, char_set: Union[set, List]) -> List[str]:
    char_list = [str(c) for c in char_set]
    result = []
    def backtrack(current_str: str, current_idx: int):
        if current_idx == len(s):
            result.append(current_str)
            return
        if s[current_idx] == '#':
            # 遇到#则尝试所有可选字符
            for c in char_list:
                backtrack(current_str + c, current_idx + 1)
        else:
            # 普通字符直接拼接
            backtrack(current_str + s[current_idx], current_idx + 1)
    backtrack("", 0)
    return result

测试验证 #

示例1测试 #

输入：

print(generate_all_combinations("a#b", {1,2,3}))

输出：
['a1b', 'a2b', 'a3b']

示例2测试 #

输入：

print(generate_all_combinations("##b", {1,2}))

输出：
['11b', '12b', '21b', '22b']

多#场景测试 #

输入：

print(generate_all_combinations("a#bcd#ef#", {'x','y'}))

输出共8组结果，符合2^3的组合预期。

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