从排序字符串中获得字母顺序的顺序复杂度提高

你检查的字符串对比你需要的多。您只需要检查连续的字符串对,而不是所有的字符串对。通过比较字符串0和3得到的信息是通过0-1、1-2和2-3比较得到的,拓扑排序可以为您处理它。拓扑排序应该运行 更快 输入中的无关边也较少。

一直在研究实际的实现,但是@user2357112已经解释了它的要点。由于列表已经按字典排序,可以简单地在迭代列表的同时跟踪最后一个单词的第一个字母,如果它与当前单词的第一个字母相同,那么把当前单词的其余部分放在列表中,直到当前单词的第一个字母与最后一个单词的第一个字母不同。此时,传递列表以进行递归调用。这个实现的平均时间复杂度将是O(n*log(n))。

collections.deque 为了高效 popleft

from collections import deque
def build_ordered_pairs(words):
    output = []
    if len(words) < 2:
        return output
    last_letter = None
    same_prefix = deque()
    while words:
        letter, *rest = words.popleft()
        if letter == last_letter:
            same_prefix.append(rest)
        else:
            if last_letter:
                output.append((last_letter, letter))
            output.extend(build_ordered_pairs(same_prefix))
            same_prefix = deque([rest])
        last_letter = letter
    output.extend(build_ordered_pairs(same_prefix))
    return output

以便:

words = deque(["baa", "abcd", "abca", "cab", "cad"])
print(build_ordered_pairs(words))

将输出:

[('b', 'a'), ('a', 'c'), ('d', 'a'), ('b', 'd')]

因为您已经知道拓扑排序,所以我不详细说明实现的其余部分。