What would be the fastest way to sort an array of words containing a-z and spaces only?
algorithm, sorting
Solution
You can put all the words in a trie (or a radix tree), and then print it in a DFS order, starting from the "smaller" lexicographical letter at each level in the DFS.
This solution will be `O(n* |S|)` where `|S|` is the average string length.
Simple example:
Let the set of strings be `[ac,ab,aca]`:
The resulting trie will be:
a
/ \
/ \
b c
| / \
$ $ a
|
$
And a DFS (which prefers lexicographically smaller characters): The DFS will start from `a`, go to `b`, and then to the end sign (`$`) and will first print `ab`, then go back to `a`, and right to `c`, and to the next `$` sign, and will print `ac`, and next to `a` and its `$` and will print `aca`, resulting in printing:
ab
ac
aca
As expexted.
Problem
I'd like to know if there's some faster way to sort such array than quicksort/mergesort. Maximum array's length is 10^6. Word's length is >=10 and <= 100 and the word can contain a-z and spaces (27 different characters in total). Characters are not unique in the words (they can repeat). All the words in an array are equally long.