字典序排序O(m)

Question

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

对algos的思考：

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

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

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

要被标记为最佳，要么从上面的3个中选择一个并解释为什么它有效，而其他的不是~，或者包括一个好的算法的链接，或者提供答案~关于如何设计在这个时间约束下工作的算法？

Answer 1

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

当一些字符串变得太短而不能包含您正在排序的数字时，您可以将它们移到当前区域的前面并忘记它们，这样它们就会留在所有以它们为前缀的较长字符串之前。

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