Given an array of strings, find if the strings can be chained to form a circle

Given an array of strings, find if the given strings can be chained to form a circle. A string X can be put before another string Y in circle if the last character of X is same as first character of Y.
Examples:
Input: arr[] = {"geek", "king"}
Output: Yes, the given strings can be chained.
Note that the last character of first string is same as first character of second string and vice versa is also true.

Input: arr[] = {"for", "geek", "rig", "kaf"}
Output: Yes, the given strings can be chained.
The strings can be chained as "for", "rig", "geek" and "kaf"

Input: arr[] = {"aab", "bac", "aaa", "cda"}
Output: Yes, the given strings can be chained.
The strings can be chained as "aaa", "aab", "bac" and "cda"

Input: arr[] = {"aaa", "bbb", "baa", "aab"};
Output: Yes, the given strings can be chained.
The strings can be chained as "aaa", "aab", "bbb" and "baa"

Input: arr[] = {"aaa"};
Output: Yes

Input: arr[] = {"aaa", "bbb"};
Output: No

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace ConsoleApplication1
{
    class Program
    {
        public static bool flag = false;
        public static ArrayList traversalList = new ArrayList();
        static void Main(string[] args)
        {
            string[] str = { "fr", "rx", "rg", "gr", "xf" };
            ArrayList al = new ArrayList(str);
            Traversal(al, char.Parse(al[0].ToString().Substring(0, 1)), char.Parse(al[0].ToString().Substring(0, 1)));
            Console.WriteLine(flag);
            foreach (string s in traversalList)
            {
                Console.WriteLine(s);
            }
        }

        public static void Traversal(ArrayList al, char start, char ch)
        {
            if(al.Count == 0 && start == ch)
            {
                flag = true;
                return;
            }
            else
            {
                for(int i = 0; i < al.Count && flag == false; i++)
                {
                    if(al[i].ToString().StartsWith(ch.ToString()))
                    {
                        ArrayList tempAl = new ArrayList(al);
                        tempAl.RemoveAt(i);
                        traversalList.Add(al[i]);
                        Traversal(tempAl, start, char.Parse(al[i].ToString().Substring(al[i].ToString().Length - 1, 1)));
                        if (flag == false)
                        {
                            traversalList.Remove(al[i]);
                        }
                    }
                }
            }
        }
    }
}

Output
=======
True
fr
rg
gr
rx
xf
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s