string - 字典排序 O(m)

Question

假设我们有 n 个字符串(英文为 26)。字符串的长度为 l1、l2、l3、... ln >= 1。令 m = sum(l1,l2,l3,...,ln)。如何在时间 O(m) 内以图形方式对字符串进行词典排序？

关于算法的思考:

选项 1:创建一个 BST，我们通过比较字母来插入单词，然后让最左边的字母按字母顺序排列在第一个，最右边的字母按字母顺序/字典顺序排列在最后一个。

选项 2:基数排序，我们有 'A' 到 'Z' 的桶......我认为如果 MSB 基数排序也就是从第一个字母开始然后填充每个字符串直到最长的字母可能不是 O(longest string length) 。 ..

选项 3:我认为 Tries 是一回事，但不确定它们的时间复杂度是否适用于此？

要被标记为最佳，请选择以上 3 个中的一个并解释为什么它有效而其他无效 ~ 或包括一个好的算法的链接或提供答案~ 你将如何设计在这个时间限制下工作的算法？

Answer 1

最简单的方法是进行最重要字符优先基数排序。

当某些字符串变得太短而无法包含您要排序的数字时，您将它们移到当前区域的前面并忘记它们，因此它们将位于所有以它们为前缀的较长字符串之前。

每个字符串的每个字符被认为是 O(1) 次，这导致总共 O(sum(lengths))(假定每个长度 >=1)