String *A *can be *chained* with string* B *, if the* last* letter of *A *matches with the* first* letter of *B*. For example “GIRI” can be chained with “IDLE”. This can be generalized to a list of strings, string*1 *chains with string*2* which in turn chains with string*3* and so on.

Now, Given a list of *n *strings find if they can be chained together . Note that this is YES/NO question, i.e; you need not come up with the actual order of chaining.

Try to come up with *O(n)* solution.

### Like this:

Like Loading...

This entry was posted on November 30, 2009 at 7:42 am and is filed under Algorithmic Questions. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

January 5, 2010 at 10:17 am |

I assume we are talking about english alphabet and so “26” size alphabet.

Prepare two 26-length arrays storing the number of words starting with a,b,c,..z and storing the number of words ending with a,b,..z

This can be done in O(n)

The answer is YES iff for 24 values out of 26, we have number of words beginning is number of words ending and for the other two values, say y and z, we have three positive cases:

y(beginning) = y(ending) and z(beginning) = z(ending)

y(beginning) = y(ending) +1 and z(beginning) + 1 = z(ending)

y(beginning) +1 = y(ending) and z(beginning) = z(ending) + 1

We can do this in O(1)

So, we can answer in O(n) in all. 🙂

I think why this would work proof is simple.

Nice!! Took me a lot of time to think.

January 5, 2010 at 11:14 am |

@Pratik ( as if i hav many commentators 🙂 )

Quick Comment:

If strings are AMMA , DAD .

these two strings satisfy the conditions u mentioned.

But they can’t be chained together.

Wat do u say?

January 5, 2010 at 9:29 pm |

You are correct.. sorry…

Please correct me. 😦

January 9, 2010 at 6:30 am |

@Pratik : Sorry for late reply.

Only first letter ,F,and last letter,L, of a string are of significance.

Let us view each ordered pair as a fraction F/L.

And we multiply all these fractions following arithmetic almost similar to numbers. ( canceling a letter if it appears in numerator and denominator, but we don’t cancel numerator and denominator of the same fraction.)

For example, if GIG, GIRI and IDLE are strings, then our fractions are G/G* G/I * I/E = G/E ( G in the result is first letter of GIG, and E is last letter of IDLE)

For a set of strings to get chained together it is NECESSARY that we are left with a fraction with SINGLE letter in the numerator and denominator.

But it is not SUFFICIENT.

Now, View each string as ordered pair(F,L).

Let us consider each ordered pair (F, L) as an vertex of a undirected graph, with edge between node A(a,b) and node B(b, c) ( last letter of A is equal to first letter of B, hence we draw edge between A and B) .

Now, for set of strings to get chained together it is also necessary that above graph is CONNECTED.

Both of these conditions together are sufficient.

We need to construct graph here, i don’t think it can be done in O(n) time, wat do u say ?? Shud i modify the question ?

( if so, sorry for misleading )

January 9, 2010 at 11:39 am |

Thanx..

I think this solution is correct:

Prepare the graph in a different way. My graph has 26 nodes. If there is a word x***y, I have an edge from x to y. Graph can be made in O(n)

Problem is to find whether or not there exists a euler path for the graph. This again can be done in O(n) 🙂

Hence solved 🙂 🙂

January 9, 2010 at 12:13 pm |

Euler path flashed for a moment when i tried to solve this,

bud didn’t carry that thread of reasoning.

Thanks for the Connection.