java - 字符串的线性时间排序算法？

Question

我有一个字符串数组，每个字符串的长度都不同。例如:

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

有什么建议吗？时间复杂度是算法的本质要求。

Answer 1

有一个数据结构叫做 trie 最适合这个。如果将所有单词插入到 trie 中，然后对 trie 执行 DFS，您将按排序顺序取回单词。这样做也需要时间 O(n)，其中 n 是所有字符串中的字符总数。

由于我认为这是家庭作业，所以我将把如何实现 trie 的细节作为练习。 :-)

希望这对您有所帮助!