Checking if a list of strings can be chained

The problem is to check if a Eulerian path exists in the directed graph whose vertices are the letters occurring as first or last letter of at least one of the supplied words and whose edges are the supplied words (each word is the edge from its first letter to its last).

Some necessary conditions for the existence of Eulerian paths in such graphs:

1. The graph has to be connected.
2. All vertices with at most two exceptions have equally many incoming and outgoing edges. If exceptional vertices exist, there are exactly two, one of them has one more outgoing edge than incoming, the other has one more incoming edge than outgoing.

The necessity is easily seen: If a graph has Eulerian paths, any such path meets all vertices except the isolated vertices (neither outgoing nor incoming edges). By construction, there are no isolated vertices in the graph under consideration here. In a Eulerian path, every time a vertex is visited, except the start and end, one incoming edge and one outgoing edge is used, so each vertex with the possible exception of the starting and ending vertex has equally many incoming and outgoing edges. The starting vertex has one more outgoing edge than incoming and the ending vertex one more incoming edge than outgoing unless the Eulerian path is a cycle, in which case all vertices have equally many incoming and outgoing edges.

Now the important thing is that these conditions are also sufficient. One can prove that by induction on the number of edges.

That allows for a very efficient check:

• record all edges and vertices as obtained from the words
• use a union find structure/algorithm to count the connected components of the graph
• record indegree - outdegree for all vertices

If number of components > 1 or there is (at least) one vertex with |indegree - outdegree| > 1 or there are more than two vertices with indegree != outdegree, the words are not chainable, otherwise they are.

Isn't that similar to the infamous traveling salesman problem?

If you have n strings, you can construct a graph out of them, where each node corresponds to one string. You construct the edges the following way:

• If string (resp. node) a and b are chainable, you introduce an edge a -> b with weight 1.
• For all unchainable strings (resp. nodes) a and b, you introduce an edge a -> b with weight n.

Then, all your strings are chainable (without repetition) if and only if you can find an optimal TSP route in the graph whose weight is less than 2n.

Note: Your problem is actually simpler than TSP, since you always can transform string chaining into TSP, but not necessarily the other way around.

Here's a case where your algorithm doesn't work:

ship
pass
lion
nail

Your start and end lists are both s, p, l, n, but you can't make a single chain (you get two chains - ship->pass and lion->nail).

A recursive search is probably going to be best - pick a starting word (1), and, for each word that can follow it (2), try to solve the smaller problem of creating a chain starting with (2) that contains all of the words except (1).