如何以有效的方式将单词列表转换为邻接列表

Question

假设我有一个单词列表。如果一个单词的最后一个字母与另一个单词的第一个字母相同，那么我们就可以将它们连接在一起。我们不连接单词 itself.The 输入元素是不同的。

示例：苹果 - 大象 - 塔 - 排名

我是这样实现的。

def transform(lst):
    graph = []
    for picked in lst:
        link = []
        i = lst.index(picked)
        rest = lst[:i]+lst[i+1:]
        for compare in rest:
            if picked[-1] == compare[0]:
                link.append(compare)
        if len(link) != 0:
            graph.append(link)
    return graph

不知道还能不能改进

============================================= ==========================

我想我应该改变

if len(link) != 0: graph.append(link)

到

graph.append(link)

否则相邻列表的顺序会乱

Answer 1

有趣！我希望我明白你在说什么。

def transform(lst):
    graph = []
    for picked in lst:
        if len(graph)==0:
            graph.append(picked)
        else:
            ch=graph[len(graph)-1][len(graph[len(graph)-1])-1]
            world_ch=[i for i in lst if ((i not in graph)and(i[0]==ch)) ]
            if len(world_ch)==0: break
            else: graph.append(world_ch[0])
    return(graph)

lista=['apple','carloh','horse','apple','elephant','tower','rank']

print(str(transform(lista)))

['apple', 'elephant', 'tower', 'rank']

print(str([[i] for i in transform(lista)]))

[['apple'], ['elephant'], ['tower'], ['rank']]

Answer 2

您应该首先确定您在此处分组的两件事。结束字母和开始字母。将所有单词放入两个字典中，分别输入关键字，您最终会得到多更快的查找。 list.index 是效率的杀手，每次查找的成本为 O(n)

from collections import defaultdict

startswith, endswith = defaultdict(list), defaultdict(list)

wordlist = ['apple','elephant','tower','rank']
for word in wordlist:
    startswith[word[0]].append(word)
    endswith[word[-1]].append(word)

那么应该是一个比较简单的图遍历问题

如何以有效的方式将单词列表转换为邻接列表

How to convert a list of words to adjacency lists in an efficient way

python

graph

adjacency-list