Given an array of strings, return true if each row can be connected to another

Question

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

The condition for connection is if the last character of one line corresponds to the first character of the second line, then the two lines can be connected .

Example: String []arr ={"abc", "cde", "cad" , "def" , "eac"} will return true , because all lines 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 a possible chain, but "acb" is not taken into account.

Note No need to start from the first line and form a chain. It may happen that you do not get the chain if you start from the first line. You can get a chain if you start from any other line. If there is a possible chain, then your decision should return true.

In the second example, if the first String were to be "fcb" , then there would be a possible chain, "cde"->"ead"->"def"->"fcb" , so True .

POSSIBLE SOLUTION (what I think): consider each line as a Node graph and connect the nodes if the condition is met. After that, the problem boils down to searching,

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

Anyone suggest any algorithm or any other solutions?

Answer 1

You do not look at the Hamiltonian cycle (i.e. beggining = start), but at the Hamiltonian path, which is also NP-Complete. However, your graphs are not common, as there are only 26 letters. If you allow more characters than 26 letters, then this is actually equivalent to the Hamiltonian path.

Here is the solution: you should consider the opposite:

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

Therefore, what you get is actually a multigraph, because several words can begin and end with the same letter. Then what you are looking for is called the Eulerian path : this is the path that each edge takes exactly once. Finding the Euler path is a polynomial problem ( https://en.wikipedia.org/wiki/Eulerian_path ). In fact, this is probably one of the first graphics problems in history.

Now referring to Wikipedia:

A directed graph has an Euler trace if and only if at most one vertex has (outside degrees) - (in degrees) = 1, at most one vertex has (in degrees) - (out-degree) = 1, each other vertex has equal degree and degree, and all its vertices with a nonzero degree belong to one connected component of the underlying undirected graph.

This is a much better way to decide if there is a way than finding Hamilton's way.

Answer 2

A similar question here: Detecting when matrix multiplication is possible

You can solve it as a problem of the Euler path, which is much simpler than the path of the Hamiltonian.

Instead of making each line a node on the graph, make each letter a node on the graph. Add a directional edge between the two letters if the line starts with the first letter and ends in the other. Now finding the Euler path in this graph will give you the necessary solution.

Answer 3

Suppose you have an alphabet of size 26.

Think of your words as a directed graph with 26 vertices corresponding to all the letters {a, b, ..., z}.

For each word that you have, add a directed edge to the graph - from the letter that starts the word to the letter that ends it.

Then you look for the Euler Path of this graph - the path that visits each edge (passes through each of your words) exactly once.

There is a well-known theorem:

A directed graph G at n vertices has a Euler Path iff. at least n-1 vertices have an incoming degree equal to the outgoing degree.

In addition, there are algorithms for constructing such a tour in polynomial time, for example, the Fleury algorithm.