单词列表中最长的单词链

Question

所以，这是我要做的函数的一部分。在

我不想代码太复杂。在

我有一个单词表，例如

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

单词链序列的概念是下一个单词从最后一个单词结束的字母开始。在

（编辑：每个单词不能重复使用。除此之外，没有其他约束。）

我希望输出给出最长的词链序列，在本例中为：

^{pr2}$

我真的不知道该怎么做，我尝试了不同的尝试。其中一个。。。在

如果我们从列表中的某个特定单词开始，例如单词[0]（所以是“长颈鹿”），则此代码可以正确地找到单词链：

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次尝试，我想这一次打印的是一个空列表，在此之前我有过不同的尝试，但都没有正确地清除单词链列表，最后又重复了一次单词。在

非常感谢你的帮助。希望我没有把这件事弄得太复杂或令人困惑。。。谢谢！在

Answer 1

正如其他人提到的，问题是找到longest path in a directed acyclic graph。在

对于Python中与图形相关的任何东西，networkx是您的朋友。在

您只需初始化图形，添加节点，添加边并启动^{}：

import networkx as nx
import matplotlib.pyplot as plt

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

G = nx.DiGraph()
G.add_nodes_from(words)

for word1 in words:
    for word2 in words:
        if word1 != word2 and word1[-1] == word2[0]:
            G.add_edge(word1, word2)
nx.draw_networkx(G)
plt.show()
print(nx.algorithms.dag.dag_longest_path(G))

It输出：

^{pr2}$

注意：此算法仅在图中没有循环（循环）时有效。这意味着它将以['ab', 'ba']失败，因为有一条无限长的路径：['ab', 'ba', 'ab', 'ba', 'ab', 'ba', ...]

Answer 2

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

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)

输出：

^{pr2}$

此解决方案的工作原理与宽度优先搜索类似，因为只要当前值以前没有被调用，函数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']

Answer 3

我有一个新的想法，如图所示：

我们可以用word[0]==word[-1]构造有向图，然后将问题转化为求最大长度路径。在