使用排列法基于替换字典生成所有可能单词的技术问询

需求是根据给定的替换字典，替换输入字符串中的字符，生成所有可能的单词组合。比如：

• 输入字符串 sap，替换字典 {'a':'b', 'b':'a', 'm':'n', 'n':'m', 'p':'q', 'q':'p'}，输出结果为 ['sap', 'saq', 'sbp', 'sbq']
• 输入字符串 map，输出结果为 ['map', 'maq', 'mbp', 'mbq', 'nap', 'naq', 'nbp', 'nbq']

解决方案 #

核心思路是对字符串中的每个字符，收集其所有可能的取值（原字符 + 替换字典中对应的字符，若存在），再通过笛卡尔积生成所有组合，最后拼接成完整单词。

用Python实现的代码如下：

import itertools

def generate_all_words(input_str, replacements):
    # 为每个字符生成可选值列表
    char_options = []
    for char in input_str:
        if char in replacements:
            # 包含原字符和替换字符
            char_options.append([char, replacements[char]])
        else:
            # 只有原字符一种选择
            char_options.append([char])
    # 生成所有笛卡尔积组合并拼接成字符串
    return [''.join(combination) for combination in itertools.product(*char_options)]

# 测试示例
replacements = {'a':'b', 'b':'a', 'm':'n', 'n':'m', 'p':'q', 'q':'p'}
x = 'sap'
print(generate_all_words(x, replacements))  # 输出: ['sap', 'saq', 'sbp', 'sbq']

y = 'map'
print(generate_all_words(y, replacements))  # 输出: ['map', 'maq', 'mbp', 'mbq', 'nap', 'naq', 'nbp', 'nbq']

代码说明 #

1. 字符可选值收集：遍历输入字符串的每个字符，若字符在替换字典中，则生成包含原字符和替换值的列表；否则仅保留原字符的列表。
2. 笛卡尔积生成组合：使用itertools.product对所有字符的可选值列表做笛卡尔积，得到所有可能的字符组合。
3. 拼接成单词：将每个字符组合拼接为字符串，最终返回所有单词的列表。

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