8

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?

Mr. Hargrove
  • 519
  • 1
  • 6
  • 26
roger_that
  • 9,493
  • 18
  • 66
  • 102

3 Answers3

7

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.

hivert
  • 10,579
  • 3
  • 31
  • 56
  • I don't think your comment about Eulerian path is helpful(slightly different problem), or provides any additional insight, good call on the Path vs Cycle thing though +1 for that. – MobA11y Jul 17 '13 at 17:25
  • Either I don't understand the problem, or it give a perfectly correct answer. Can you explain me why the problems are different ? – hivert Jul 17 '13 at 17:30
  • Yes. I understand your point as well. My intent of saying about Hamiltonian cycle was that in the questions, where it says its not necessary to start with first string and find a chain, so probably that is why i thought of connecting nodes to a graph and then proceed. Meanwhile, i would love to get any other solution or a way to it. – roger_that Jul 17 '13 at 17:30
  • 1
    Hamiltonian algorithms are well documented, and there is a concise set of properties of a graph you can look at if all you need is "true/false" and no actual path. – MobA11y Jul 17 '13 at 17:32
  • 1
    @ChrisCM. I don't agree that the correct one was already chosen. Finding Hamiltonian path is a hard problem (NP) whereas finding Eulerian path is a very easy one (P). I'm pointing out that OP problem can be both encoded as an Hamiltonian path and an Eulerian path problem. If you want to solve it is is better to encode it to a simpler problem. – hivert Jul 17 '13 at 17:38
  • 1
    yeah, And we only need to verify if the path exists. We don't need the actual path here. – roger_that Jul 17 '13 at 17:41
  • Is it me, or were you the one continuing the conversation and I simply answering your questions...? It's an acceptable, actually good answer got my upvote! But given the fact that no path is actually necessary just validation, and the OP has already considered it as a hamilton path, your answer adds nothing to his and if he wants to think of it this way we shouldn't discourage him from doing so... Sorry. – MobA11y Jul 17 '13 at 17:51
  • @ChrisCM it is indeed a correct answer until you try to implement an Hamiltonian path decider... – hivert Jul 17 '13 at 17:54
  • Both problems are well documented. You could get a prefab algorithm to do both in a matter of seconds, if they still allowed lmgtfy links, I would be happy to post a couple for you :) – MobA11y Jul 17 '13 at 17:56
  • No, Hamilton path has nothing to do with this problem because Hamilton paths aren't required to use all of the edges, multigraph or not. – David Eisenstat Jul 17 '13 at 19:30
0

Similar question answered here: Detecting when matrix multiplication is possible

You can solve it as Eulerian path problem which is much simpler than a hamiltonian path.

Instead of making each string a node in the graph, make each letter a node in the graph. Add a directed edge between two letters if a string starts in the first letter and ends in the other. Now finding a Eulerian path in this graph would give you the required solution.

Community
  • 1
  • 1
ElKamina
  • 7,747
  • 28
  • 43
0

Let's assume, that you have an alphabet of size 26.

Let's think of your words as a directed graph with 26 vertices corresponding to all letters {a, b, ..., z}.

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

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

There is a famous theorem:

The directed graph G on n vertices has an Euler Path iff. at least n-1 vertices have incoming degree equals outgoing degree.

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

pkacprzak
  • 5,537
  • 1
  • 17
  • 37