0

How can I design an algorithm to sort n strings in O(dn) where d is the #of characters in a longest string?

Mitch Wheat
  • 295,962
  • 43
  • 465
  • 541
Faisal Al-harthi
  • 5
  • 1

1 Answers1

1

You can use a trie.

  1. Create an empty trie.

  2. Loop over all strings, and place them in it.

  3. Iterate over all the trie's values in order, and output them (see Trie complexity and searching as suggested below by Jean-Baptiste Yunès).

The complexity of 1 is constant. The complexity of each of 2 and 3 is O(dn).

Community
  • 1
  • 1
Ami Tavory
  • 74,578
  • 11
  • 141
  • 185
  • 3rd point is not clear. How are you making sure the strings are sorted – Saurav Sahu Oct 05 '16 at 07:28
  • @SauravSahu It's a pretty simple recursive function (see [here](http://stackoverflow.com/questions/13685687/how-to-print-all-words-in-a-trie) an implementation). Starting at the node, recursively visit all children in order, while keeping track of current prefix. When you hit a leaf, output the total string along the path. – Ami Tavory Oct 05 '16 at 07:51
  • Complement: http://stackoverflow.com/questions/13032116/trie-complexity-and-searching – Jean-Baptiste Yunès Oct 05 '16 at 08:05
  • @Jean-BaptisteYunès Thanks for the useful link! Added inline – Ami Tavory Oct 05 '16 at 08:08