CODEWITHSUNDEEP
stringalgorithmsortingtreelexicographic
Sudocode
Sudocode

Reputation: 79

Lexicographic sort O(m)

Suppose we have n strings of characters (26 in English). The lengths of the strings are l1, l2, l3, ... ln >= 1. Let m = sum(l1,l2,l3,...,ln). How to sort the strings lexico graphically in time O(m)?

Thoughts on algos:

Option 1: Create a BST where we insert words by comparing their letters and then having the left most be the first alphabetical and rightmost be the last in alphabetical/ lexicographically.

Option 2: Radix Sort where we have buckets for 'A' to 'Z' ... I think if do the MSB radix sort aka start with the first letter then pad each string till the longest letter that might not be O(longest string length) ...

Option 3: I think Tries are a thing but not sure about if their time complexity works for this?

To be marked best either pick one of the 3 above and explain why it works and others not ~ or include a link to a good algo or provide answer~ on how you would design the algo that works under this time constraint?

Upvotes: 1

Views: 987

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59253

The easiest way is to do a most-significant-char-first radix sort.

When some strings become too short to contain the digit you're sorting on, you move them to the front of the current region and forget about them, so they will stay before all of the longer strings that have them as prefixes.

Each character of each string is considered O(1) times, which leads to O(sum(lengths)) in total (given that each length is >=1)

Upvotes: 1

Related Questions