Given an array of Strings, return true if each string could be connected to other

Question

You are given an array of strings, return true if and only if all the strings can be connected in one chain.

Condition for connectivity is, if the last character of one string matches the first character of the second string, then the two strings can be connected.

Example : String []arr ={"abc", "cde", "cad" , "def" , "eac"} will return true because all strings can be connected in one chain.

"abc"->"cde"->"eac"->"cad"->"def"

Another Example: String []arr ={"acb" , "cde", "def", "ead" } returns False because
"cde"->"ead"->"def" is the possible chain but “acb” is left out.

Note: It's not necessary to start with the first string and form the chain, It may happen that you won’t get a chain if you start with the first string. You can get a chain if you start with any other string. If there exists a possible chain, then your solution should return true.

In the second example, if the first String was suppose to be “fcb”, then a possible chain would have existed, "cde"->"ead"->"def"->"fcb" so True.

POSSIBLE SOLUTION (what i am thinking): Consider each string as a graph Node and connect the nodes if condition is satisfied. Once done, problem reduces to finding,

if there exists a Hamiltonian Cycle in a graph, which is NP-Complete problem.

Anyone suggest some algorithm or any other solutions?

Answer 1

Your are not looking to an Hamiltonian Cycle (ie beggining = start) but an Hamiltonian path which is an NP-Complete problem too. However, your graphs are not general one since there are only 26 letters. If you allows for more symbol than 26 letters then it is actually equivalent to Hamiltonian path finding.

Here is a solution: you should think the converse way:

• the vertex of the graph are the 26 letters.
• There is an edge between letter x and y for each word starting with x and ending with y

Therefore what you get is actually a multigraph as several word can start and end with the same letter. Then what you are looking is called an Eulerian path: it is a path which takes each edges exactly one time. Finding an Eulerian path is a polynomial problem (https://en.wikipedia.org/wiki/Eulerian_path). It is actually probably one of the first graph problem in history.

Now citing Wikipedia:

A directed graph has an Eulerian trail if and only if at most one vertex has (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree, and all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph.

This is a far better way to decide if there is a path than searching for an Hamiltonian path.