python - 提高从已排序字符串中获取字母顺序的顺序复杂度

Question

假设我有一个按字典顺序排序的字符串(最大大小为 m)的列表(大小为 n)，由 a-z 组成，但不是 a、b、c 的词汇顺序。 ..。现在的主要问题是我想找到字母表的顺序。所以我把问题分成两部分:

1. 从列表中的字符串中找到有序的字母对。
2. 从这些对作为边构造一个有向图。对图进行拓扑排序以获得顺序。

我的问题是关于第一个。

为了做 1.，我做了一个 O(n^2m) 循环:

vector<pair<char, char> > build_ordered_pairs(vector<string> words) {
    vector<pair<char, char> > ordered_pairs;
    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            k = 0;
            while(k < words[i].size() && k < words[j].size() && words[i][k] == words[j][k])
                k++;
            if(k < words[i].size() && k < words[j].size())
                ordered_pairs.push_back(make_pair(words[i][k], words[j][k]));
        }
    }
    return ordered_pairs;
}

为了改进这一点，我们可以将字符串放在 trie 中，然后从 trie 的每个级别获取对。但这又是 n 的二次方。我们可以做得更好吗，比如 nlogn 或 n？

我们可能会一次又一次地得到相同的双鞋。那么我们是否可以检查不需要某个对，因此我们可以在同时构建有向图时跳过它。提前致谢。

示例输入输出对:

words = {"baa", "abcd", "abca", "cab", "cad"}
required = {'b', 'd', 'a', 'c'}

P.S:也标记为 python，因为两者的解决方案/建议都对我有用。

Answer 1

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