Algorithmic Question : 1

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, string1 chains with string2 which in turn chains with string3 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.


6 Responses to “Algorithmic Question : 1”

  1. Pratik Poddar Says:

    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.

  2. connect2ppl Says:

    @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?

  3. Pratik Poddar Says:

    You are correct.. sorry…
    Please correct me. 😦

  4. connect2ppl Says:

    @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 )

  5. Pratik Poddar Says:

    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 🙂 🙂

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: