字典排序 O(m)
Lexicographic sort O(m)
假设我们有n个字符串（英文26个）。字符串的长度为 l1、l2、l3、... ln >= 1。令 m = sum(l1,l2,l3,...,ln)。如何在时间 O(m) 内以图形方式对字符串词典进行排序？
对算法的思考：
选项 1：
创建一个 BST，我们通过比较字母来插入单词，然后让最左边的字母按字母顺序排列，最右边的字母按字母顺序/字典顺序排列在最后一个。
选项 2：
基数排序，我们有 'A' 到 'Z' 的桶...我想如果 MSB 基数排序也就是从第一个字母开始然后填充每个字符串直到最长的字母可能不是 O(longest字符串长度) ...
选项 3：
我认为 Tries 是一回事，但不确定他们的时间复杂度是否适用于此？
要标记得最好，请选择以上 3 个中的一个并解释为什么它有效而其他无效 ~ 或者在一个好的算法中包含一个 link 或提供答案~ 你将如何设计有效的算法在这个时间限制下？
最简单的方法是进行 most-significant-char-first 基数排序。
当某些字符串变得太短而无法包含您要排序的数字时，您将它们移至当前区域的前面并忘记它们，因此它们将位于所有具有它们的较长字符串之前前缀。
每个字符串的每个字符被认为是 O(1) 次，这导致总共 O(sum(lengths))（假设每个长度 >=1）
假设我们有n个字符串（英文26个）。字符串的长度为 l1、l2、l3、... ln >= 1。令 m = sum(l1,l2,l3,...,ln)。如何在时间 O(m) 内以图形方式对字符串词典进行排序？
对算法的思考：
选项 1： 创建一个 BST，我们通过比较字母来插入单词，然后让最左边的字母按字母顺序排列，最右边的字母按字母顺序/字典顺序排列在最后一个。
选项 2： 基数排序，我们有 'A' 到 'Z' 的桶...我想如果 MSB 基数排序也就是从第一个字母开始然后填充每个字符串直到最长的字母可能不是 O(longest字符串长度) ...
选项 3： 我认为 Tries 是一回事，但不确定他们的时间复杂度是否适用于此？
要标记得最好，请选择以上 3 个中的一个并解释为什么它有效而其他无效 ~ 或者在一个好的算法中包含一个 link 或提供答案~ 你将如何设计有效的算法在这个时间限制下？
最简单的方法是进行 most-significant-char-first 基数排序。
当某些字符串变得太短而无法包含您要排序的数字时，您将它们移至当前区域的前面并忘记它们，因此它们将位于所有具有它们的较长字符串之前前缀。
每个字符串的每个字符被认为是 O(1) 次，这导致总共 O(sum(lengths))（假设每个长度 >=1）