PROBLEM LINKS:
Practice:https://www.codechef.com/COEX1601/problems/COEX04
Contest:https://www.codechef.com/problems/COEX04
DIFFICULTY:
MEDIUM
PREREQUISITES:
Strings
PROBLEM:
Given a number of words, check if it is possible to arrange them in an order such that the last alphabet of the word is the first alphabet of the word that follows it.
EXPLANATION:
Step 1: Store all the starting and ending alphabets of the given ‘n’ words in two character arrays, say start and end respectively.
Step 2: If the end alphabet of the word is the first alphabet of the word that follows it, let’s call such a combination a link.
Step 3: flag array is used to keep track of all used alphabets in start. Used alphabets are marked 1 and unused ones are marked zero.
Step 4: Starting from the first index of end, all the indexes of start are searched for the matching alphabet.
Step 5:If matching index is found, then we check that it does not belong to the same word, and also that it has not been used first by checking flag for it. If it has not been used first and does not belong to the same word,we use the start of this word and repeat the Step 4 after flagging this word and incrementing links by 1.
Step 6: If matching index belongs to same word or has been flagged, we search the subsequent indexes for a match. If found, step 5 is followed.
Step 7: If no matching index is found, we use the next end index and repeat step 4.
for(k=0 to k=n-1 increment by 1)
{
i=start.find(end[index]);
if(i!=index && flag[i]!=0)
{
flag[i]=0;
index=i;
links=links+1;
}
else if(i==index)
{
i=start.find(end[index],i+1);
if(flag[i]!=0)
{
flag[i]=0;
index=i;
links=links+1;
}
else
break;
}
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.