时间戳

首页 > 解决方案 > 单词列表中最长的单词链

python - 单词列表中最长的单词链

问题描述

所以，这是我正在尝试制作的功能的一部分。

我不希望代码太复杂。

我有一个单词列表，例如

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

单词链序列的想法是下一个单词以最后一个单词结尾的字母开头。

（编辑：每个单词不能多次使用。除此之外没有其他限制。）

我希望输出给出最长的词链序列，在这种情况下是：

['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']

我不确定该怎么做，我尝试过不同的尝试。其中之一...

如果我们从列表中的特定单词开始，此代码会正确找到单词链，例如 words[0]（所以 'giraffe'）：

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

word_chain = []

word_chain.append(words[0])

for word in words:
    for char in word[0]:

       if char == word_chain[-1][-1]:
            word_chain.append(word)

print(word_chain)

输出：

['giraffe', 'elephant', 'tiger', 'racoon']

但是，我想找到最长的单词链（如上所述）。

我的方法：所以，我尝试使用我编写并循环的上述工作代码，使用列表中的每个单词作为起点，并为每个单词[0]、单词[1]、单词[2]找到单词链] 等。然后我尝试使用 if 语句找到最长的单词链，并将长度与之前的最长链进行比较，但我无法正确完成，我真的不知道这是怎么回事。

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']

word_chain = []
max_length = 0
for starting_word_index in range(len(words) - 1):

    word_chain.append(words[starting_word_index])

    for word in words:
        for char in word[0]:

            if char == word_chain[-1][-1]:
                word_chain.append(word)

    # Not sure

    if len(word_chain) > max_length:
        final_word_chain = word_chain
        longest = len(word_chain)
        word_chain.clear()

print(final_word_chain)

这是我的第 n 次尝试，我认为这会打印一个空列表，在此之前我进行了不同的尝试，但未能正确清除 word_chain 列表并最终再次重复单词。

非常感谢任何帮助。希望我没有让这变得太乏味或令人困惑......谢谢！

标签： pythonrecursiongraphpath-finding

解决方案

当包含正确初始字符的每个可能的字母都添加到运行列表时，您可以使用递归来探索出现的每个“分支”：

words = ['giraffe', 'elephant', 'ant', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse']
def get_results(_start, _current, _seen):
  if all(c in _seen for c in words if c[0] == _start[-1]):
    yield _current
  else:
      for i in words:
        if i[0] == _start[-1]:
          yield from get_results(i, _current+[i], _seen+[i])


new_d = [list(get_results(i, [i], []))[0] for i in words]
final_d = max([i for i in new_d if len(i) == len(set(i))], key=len)

输出：

['hedgehog', 'giraffe', 'elephant', 'tiger', 'racoon']

此解决方案的工作原理类似于广度优先搜索，get_resuls因为只要之前未调用过当前值，该函数就会继续遍历整个列表。函数已经看到的值被添加到_seen列表中，最终停止递归调用流。

此解决方案还将忽略重复的结果：

words = ['giraffe', 'elephant', 'ant', 'ning', 'tiger', 'racoon', 'cat', 'hedgehog', 'mouse',]
new_d = [list(get_results(i, [i], []))[0] for i in words]
final_d = max([i for i in new_d if len(i) == len(set(i))], key=len)

输出：

['ant', 'tiger', 'racoon', 'ning', 'giraffe', 'elephant']

推荐阅读