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

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作为练习的细节.:-)

希望这可以帮助!