我有一个字符串数组，每个字符串都有不同的长度。例如：
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 的细节留作练习。:-)
希望这可以帮助！
我有一个类似的测试问题，我弄错了，但从那时起它就一直困扰着我。所以我一直在研究它，我认为还有其他两种方法可能会在线性时间内产生结果。一种是将字符串视为一系列以 26 为底的整数，并在将字符串填充为相等长度后对数组使用基数排序（以某种方式 - 可能有一种巧妙的方法可以在不大幅增加存储空间的情况下做到这一点，我只是没有弄清楚细节）。我还没有建立一个例子或测试它，所以我不能肯定地说这会起作用，但它的原理似乎是合理的。另一种方法是桶排序 - 使用包含指向 26 个列表（桶）的指针的 26 元素数组。将每个字符串排序到适当的桶链表（那些以 'a' 到第一个数组元素指向的列表中，等等）然后使用标准的 O(n log n) 方法对每个列表进行排序。我不完全理解数学，但根据 Cormen 的教科书“算法简介”，以这种方式使用桶排序最终具有线性时间复杂度。不过，看起来空间会比 Radix 样式的方法大，只要可以满足右填充要求而无需实际为其分配一堆存储空间。
因为这是一个家庭作业问题，我只能给出一个提示。提示：使用修改后的计数排序。如果我们假设一个 char 是 8 位，这很实用。