python-3.x - 使用单词列表中的最小单词子串形成目标字符串

Question

我有一个包含名字的文本文件，但每年都会添加新名字。

我需要一个 Python 程序，它从文本文件中获取部分名称，并找到这些名称的子字符串的某种组合，这些子字符串可以连接起来以创建与用户输入匹配的字符串。

程序应该使用文本文件中尽可能少的可用名称来执行此操作。

例如，如果文本文件包含以下内容:

Joppe
Fien
Katrijn
Sven
Kobe

程序要求输入文本文件中不存在的名称。例如:

Please fill in a name: Katrien

然后它应该打印这个:

Katri => Katrijn
ien => Fien

不是这样的——它可以正确地构建名称，但是有一个使用更少单词的更好的解决方案:

K => Kobe
a => Katrijn
tr => Katrijn
ien => Fien

如果文本文件包含这个:

Joppe
Fien
Makatrijn
Sven
Kobe

它也可以打印这个:

Katr => Makatrijn
ien => Fien

我试过了，但没有结果:

name_input = input('Fill in a name: ')    

with open('namen.txt', 'r') as file:
    for name in file.readlines():
        for letter_name_input in name_input:
            for letter in name:
                if letter == letter_name_input:
                    print(letter)

Answer 1

您可以使用一个将目标名称和一组名称作为输入的函数，尝试将目标名称的前缀与名称集中的每个名称进行匹配，从最长到最短，并为每个匹配名称, 递归地从删除了匹配名称的名称集中找到将构成目标名称的名称，并删除了前缀，并产生每个返回的组合，其中当前前缀和名称作为元组前缀:

def form_name(target, names):
    if target:
        for i in range(len(target), 0, -1):
            prefix = target[:i]
            matching_names = [name for name in names if prefix.lower() in name.lower()]
            if matching_names:
                for name in matching_names:
                    for fragments in form_name(target[i:], names - {name}):
                        yield [(prefix, name), *fragments]
    else:
        yield []

这样就可以使用min函数，以len为key函数，得到最少名字的组合:

from io import StringIO
file = StringIO('''Joppe
Fien
Katrijn
Sven
Kobe''')
for fragment, name in min(form_name('Katrien', set(file.read().split())), key=len):
    print(fragment, '=>', name)

输出:

Katri => Katrijn
en => Fien

演示:https://repl.it/repls/IllustriousTrustingIntegrationtesting

请注意，您的示例输入中的 Fien 和 Sven 都将匹配 en 片段，并使用最少的名称生成有效答案，因此min 函数会任意返回其中之一(这完全符合您的要求)。另请注意，您不应期望目标名称的片段重叠，因此第二个片段应该是 en 而不是 ien 第一个片段 Katri 从目标名称 Katrien 中删除。

如果你有兴趣看到所有的有效答案，你可以先计算所有组合的最小长度，然后输出最小长度的所有组合:

combinations = list(form_name('Katrien', set(file.read().split())))
min_len = min(map(len, combinations))
for combination in combinations:
    if len(combination) == min_len:
        for fragment, name in combination:
            print(fragment, '=>', name)
        print()

这个输出:

Katri => Katrijn
en => Sven

Katri => Katrijn
en => Fien

Katr => Katrijn
ien => Fien