字符串与特定变量字符的组合

Question

如何收集字符串的组合，其中某些字符（但不是全部）是可变的？你知道吗

换句话说，我有一个输入字符串和一个字符映射。字符映射指定哪些字符是可变的，以及可以用什么替换它们。然后该函数产生所有可能的组合。你知道吗

为了更好地理解这一点，我试图收集OCR输出字符串的可能变体，这些变体可能被OCR引擎误解了。你知道吗

输入示例：

"ABCD"

字符映射示例：

dict(
    B=("X", "Z"),
    D=("E")
)

预期输出：

[
    "ABCD",
    "ABCE",
    "AXCD",
    "AXCE",
    "AZCD",
    "AZCE"
]

Answer 1

您可以使用^{}：

>>> from itertools import product
>>> s = "ABCD"
>>> d = {"B": ["X", "Z"], "D": ["E"]}
>>> poss = [[c]+d.get(c,[]) for c in s]
>>> poss
[['A'], ['B', 'X', 'Z'], ['C'], ['D', 'E']]
>>> [''.join(p) for p in product(*poss)]
['ABCD', 'ABCE', 'AXCD', 'AXCE', 'AZCD', 'AZCE']

注意，为了保持一致性，我制作了d["D"]一个列表，而不仅仅是一个字符串。你知道吗

Answer 2

我自己的解决方案非常难看，也不是Python式的，但下面是：

def fuzzy_search(string, character_map):
    all_variations = []

    for i, character in enumerate(string):
        if character in character_map:
            character_variations = list(character_map[character])
            character_variations.insert(0, character)

            if i == len(string) - 1:
                return [string[:-1] + variation for variation in character_variations]

            for variation in character_variations:
                sub_variations = fuzzy_search(string[i + 1:], character_map)

                for sub_variation in sub_variations:
                    all_variations.append(string[:i] + variation + sub_variation)

            return all_variations

    return all_variations

map = dict(
    B=("X", "Z"),
    D=("E")
)

print fuzzy_search("ABCD", map)

输出：

['ABCD', 'ABCE', 'AXCD', 'AXCE', 'AZCD', 'AZCE']

我觉得应该有比多个循环的递归函数更优雅的解决方案。你知道吗