Add-A-Gram (ITA Archived Puzzle, Analyzed)

Please refer to the add-a-gram problem on this page.

Analysis

Given a 3 letter word, let us assume, we can find out the 4 letter words that are its add-a-grams. We can then expand this to a n letter word pointing to its (n + 1)th add-a-gram. We can obviously model this as a directed graph where each word points to its add-a-grams.

Further since there is no possibility of an add-a-gram pointing to its possible source, this will be an acylic graph. Thus we have a directed acyclic graph representing the add-a-grams.

Algorithm

The problem then is of finding the ’longest path’ in the directed acyclic graph. In our case each edge will have a weight of 1.

First we build a hash table where key is the length of the word and values are the words of those length. Then we build the directed acylic graph such that each vertex is the word ’w’ and its neighbors are its add-a-grams obtained by searching through the hash table those words which are 1 more character in length than the given word ’w’.