Posts

Showing posts from November, 2014

Unique prefixes

Image
This is a problem about finding the shortest unique prefixes for a list of words.


To illustrate this, bellow is an example with the prefixes highlighted:

playingplayer
To solve this problem, we are going to implement a generic algorithm which will work for any number of words. A very fast way of doing this, is by using multidimensional hashes.

The simplest way to create a multidimensional hash, is to create a reference to the original hash, iterate over the keys you want to add and create a new hash for each key which doesn't exists inside the current hash, and change the hash reference to this new hash.

Let's define a function which takes a reference to a hash and a string. First, it splits the string into characters, then it traverses the hash, adding each character to the corresponding branch:

subadd_entry{my($ref,$word)=@_;foreachmy$char(split(//,$word)){$ref=$ref->{$char}//={};}}
Now, let's define an %hash and call the above function to add an 'word' into it: …