Checking if a list of strings can be chained

Question

Question

Implement a function bool chainable(vector<string> v), which takes a set of strings as parameters and returns true if they can be chained. Two strings can be chained if the first one ends with the same character the second starts with, e.g.:

ship->petal->lion->nick  = true;  (original input is list not LL)
ship->petal   axe->elf   = false;

My Solution:

My logic is that if its chainable there will only be one start and end that don't match. So I create a list of starts and a list of ends. like so.

starts:s,p,l,n
ends:  p,l,n,k

if I remove the common elements, the lists should contain at most one items. namely s and k. If so the list is chainable. If the list is cyclic, the final lists are empty.

But i think I am missing some cases here,

EDIT: Okay clearly I had faults in my solution. Can we conclude the best algorithm for this ?

Answer 1

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.

Answer 2

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.