我有一个字符串数组，每个字符串的长度都不同。例如:
s[0] = "sSWXk"
s[1] = "qCk"
s[2] = "sOQQXPbk"
.
.
.
s[x] = "KVfdQk";
我也知道
n = s[0].length() + s[1].length() + ... + s[x].length()
我需要一个时间复杂度为 O(n) 的排序算法来按字典顺序对这些字符串进行排序，以便(例如)
a < ab < b < bbc < c < ca
有什么建议吗？时间复杂度是算法的本质要求。
最佳答案
有一个数据结构叫做 trie 最适合这个。如果将所有单词插入到 trie 中，然后对 trie 执行 DFS，您将按排序顺序取回单词。这样做也需要时间 O(n)，其中 n 是所有字符串中的字符总数。
由于我认为这是家庭作业，所以我将把如何实现 trie 的细节作为练习。 :-)
希望这对您有所帮助!
关于java - 字符串的线性时间排序算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11003606/