longest list of words with matching start and end letters

Question

My friend gave me a problem that he says is easy, but I can't figure out a good algorithm to use to do it.

You are given an input of 100 random English words. You have to find the longest string of words where the last letter in one word matches the first letter in the next word. You can only use each word once.

For example, if you were given the words "cat", "dog", "that", the longest string you could make would be "cat -> that". If you were given the words "mouse", "moose", "unicorn", the longest string you could make would just be one word (since none of those words link). If you were given the words "bird", "dish", "harb", the longest string you could make would be "harb -> bird -> dish" (or "dish -> harb -> bird" or "bird -> dish -> harb").

I came up with the idea of modeling this as a directed cyclic graph. Each node would just be a word, with vertices going to each word/node that started with the letter this word ended with.

+-------+         \ +------+
|  cat  |-----------| that |
+-------+         / +------+
    |                  |
   \|/                 |
+-------+ /            |
|  the  |--------------+
+-------+ \

This problem appears to be a longest path search, which is NP-Hard.

Is there a better way to do it? Or even some sort of approximation algorithm that could be used? Or some way to exploit qualities of English to reduce the search space?

Answer 1

I think this is related to the longest path (LP) problem that you mentioned, but it's a little different. The primary difference is that the LP problem has a higher degree of connectivity than what your suggested problem does. By restricting your connections to the last and first letters, you remove a large number of potential combinations.

Here's how I would recommend tackling this one:

1. For each word in the list, count the possible connections in and connections out.
2. Discard any words that have 0 ins and 0 outs.
3. Identify an initial set of "starter words" with the lowest numbers of ins and outs, and the outs must be greater than 0.
4. Each starter word receives its own working copy of the ins / outs connection count. This forms the head of the chain.
5. For each chain, identify a list of "next words" based upon:
   
   • last letter of starter or previous word
   • lowest number of of ins and outs connections (again, the outs must be greater than 0)
6. For each next word, repeat step 5 until the chain terminates.

Keep in mind that:

• You'll need to keep track of the length of the chains and have some global mechanism to identify the longest chain.

• You'll also need to remove each word from the working copy of the connection counts in order to avoid a recursive loop.

• At some point, your chain will terminate and you have to select a word with a 0 connection out count.

• You may have to recalculate ins / outs as words are removed from the working lists. At first glance, I don't think this will be necessary as the overall sets will be relatively small. If you scaled out to 1000 words, then having static counts may slow down the algorithm from converging.

I kind of saw this as a packing problem. To me, the connections in and out identify the shape to be packed. The lower the connections, the more odd the shape. The more odd the shape, the sooner I want to pack it as I perceived having decreasing odds of being able to pack an odd shape the later I got into the chain.

As an example:

{dog, gopher, alpha, cube, elegant, this, that, bart}

dog     0, 1
gopher  1, 0
alpha   0, 0
cube    0, 1
elegant 1, 2
this    3, 0
that    2, 1
bart    0, 2

//alpha is dropped with 0 in and 0 out.
//two candidates found: dog, cube

//chain 1
dog => gopher
//chain 2
cube => elegant => that => this

//Note 1: the following chain won't occur due to selection rules
//that takes priority over this because of output count
cube => elegant => this

//Note 2: this chain won't occur either due to selection rules
bart => that => this

Answer 2

If you make 26X26 matrix to represent directed graph of vertex as each alphabet and words as edge. For example word - APPLE connect vertex A and E with edge directed from A to E. Now the problem reduces to finding largest Eulerian trail (path which includes maximum number of edges, visiting each edge once wit possible repetition of vertices) in the graph. One of the O(E) algorithm would be to start randomly from a pair of vertices. Find a path between them. Than keep relaxing the path till it is possible.

update @GlenH7 I solved a similar question on www.hackerearth/jda recently, there was relative marks with respect to best solution and I scored the highest marks with the following approch-

Given list of words. Find the longest chain that can be formed by them. A chain is valid if every word begin with a letter *ending at the ending of last word.

Approch =

1)make the graph of alphabets as vertices and words as edges. In place of using multiple edges use one with weight equal to number of edges.

2)find the strongly connected component of graph with maximum edges. Temporarily discard other edges.

3)For each vertex make its indegree equal to its outdegree.

4)Now their exists eulerian circuit in graph. Find it.

5)Now in remaining graph(w.r.t orignal graph find the longest trail with first vertex in chosen strongly connected component. I think this is NP hard.

6)Include the above trail in Elerian circuit converting eulerian circuit into trail.

Why - I accept that this question is most probably NP hard(guess, not mathematically speaking). But the above approach works best when there is a long list(1000+) of uniformly distributed words(i.e. not intended to be w.c. for above approach). Let us assume that after converting given list to graph mentioned above, it luckily turns out to be a eulerian graph(see http://en.wikipedia.org/wiki/Eulerian_path for conditions), then without any doubt we can say that answer to above question is P and is actually the eulerian path in the graph(see http://www.graph-magics.com/articles/euler.php for a very simple approch to do so and see this to verify that your graph has single http://www.geeksforgeeks.org/strongly-connected-components/ and if not temporarily clean other small scc because eulerian path exists for single scc). Thus for not lucky cases(which are almost all cases) I try to convert them to lucky cases(i.e eulerian trail condition are fulfilled). How to do this? I tried do increasing depth search for irrelevant edges(the set of edges in a path staring from vertex with outdegree greater than indegree and ending at vertex with indegree greater than outdegree). Increasing depth search means that first I searched for all such set of one edge in path than two edges in path and so on. It may seem at first look that ith depth search would take O(nodes^i) thus total time complexity of O(nodes + nodes^2 + nodes^3 + ....) till it is a lucky case. But amortized analysis will revel it is O(edges). Once it is reduced lucky case find eulerian circuit.

Till here it was all polynomial time. This would give almost the best solution. But to further increase your solution(perfect solution is NP hard) try some greedy approach in remaining graph to find a long trail staring with one of vertices in chosen scc. Now add this to above found eulerian trail to further increase it.

Answer 3

Idea:

First, create two maps (hashes), say, S, and E, from alphabet letters to words; the first, S, maps starting letters to words, the second, E, does the same with ending letters.

E.g., if the dictionary is made of:

bird, dish, dog, harb

we have:

S:

a -> [ ]
b -> [ bird ]
c -> [ ]
d -> [ dish, dog ]
...
h -> [ harb ]
...

and,

E:

a -> [ ]
b -> [ harb ]
c -> [ ]
d -> [ bird ]
...
g -> [ dog ]
h -> [ dish ]
...

Next, using S and E for fast lookups, create a forest (set of trees), of the same size as the dictionary, with roots at each word, and not allowing a word to appear more than once in a tree -- cache the trees' depths as you construct them:

bird (depth: 2)
   dish
      harb
   dog

dish (depth: 3)
   harb
      bird
         dog

dog (depth: 0)

harb (depth: 2)
   bird
      dish
      dog

Finally, iterate over the forest and find the tree(s) of greatest depth.

The solution(s) will be on the descendant axis of those trees.

E.g.,

dish / harb / bird / dog

above.