Showing posts from November, 2014

Unique prefixes

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: playi ng playe r 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: sub add_entry { my ( $ ref , $ word ) = @ _ ; foreach my $ char ( split ( // , $ word ) ) { $ ref = $ ref -> { $ char } //