Shortest unique prefix of a word - solved the wrong way ?

A Trie (reTrieval) is a common solution to an optimal prefix search, like one you would use in an autocomplete. It therefore make sense to use it in the following problem

Given a list of words, return the shortest unique prefix of each word.

and here is the complete problem

At this point I should mention, that this post isn't about solving the problem with a Trie

I had heard of a Trie but was not familiar with the implementation details. I therefore decided to attempt this problem without a Trie.

Understanding the problem

We are looking for prefixes that are -

  • unique
  • short

Drawing this out with a solution that has more than 2 characters puts the problem into perspective

Solving it

At first glance, it seemed obvious to me that I had to track the position in which each character occurred. I could use a map for this, where 

  • the key was the character, 
  • and the value was a set of positions

I could now traverse each character in the string, and check to see if this character existed in the same position. But wait.... I did not have enough data to tell me HOW MANY occurrences existed in the same position.

Revising the Solution

I would instead  now keep track of the occurrences too, with a map of maps.

  • The key of the outer map would be the character
  • The key of the inner map would be the position
  • The value of the inner map would the number of occurrences

At this point, I realized that this solution would be potentially memory intensive as it involves building up a map, and the problem statement did not list any constraints

With a revised map, I can now traverse the characters in each word. 

  • Characters that have more than one occurrence in the current position are saved to a candidate string 
  • The traversal is terminated when we find a character that has only one occurrence in the current position and hence a unique prefix. This character is added to the candidate string and that is our solution for that word.

I was curious to see if my approach was listed as an alternative solution, but most online solutions advocate the use of a Trie. I do plan on researching this some more and understanding it implementation details , and that will be a topic of an upcoming post.