One simple solution would be to use MSD radix sort, assuming a constant-size alphabet. Replace "digit" by "character" while reading the algorithm description. You will also need to throw out strings that are smaller than i if you are currently processing the position i, otherwise you won't get the desired runtime.
Sorting a list of names lexographically
-
15-06-2023 - |
문제
Say you are given a list of names, S = {s1, s2 ... sn} and you want to sort them lexicographically.
How would you guarantee that the running time of the sort is O(the total sum of the lengths of all the words)?
Any useful techniques?
해결책
제휴하지 않습니다 StackOverflow