Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Algorithm for the solution
3.
Implementation of the approach(C++)
3.1.
Complexity Analysis
4.
Frequently Asked Questions
5.
Key takeaways
Last Updated: Mar 27, 2024

How to check if an array of strings can form a circle or not?

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Suppose we are given an array of strings, and we are asked if we can chain the strings to form a circle which means that the last element of any string has to be the same as the first element of the next string. 

Let’s understand the problem with an example-

Suppose we have an array of strings given below- {“aabc”, “cert”, “ter”, “reha”}

In the above example, we can see that the last letter is similar to the first letter of the next string for each string. So we can form a circle from these strings. 

Whereas if we take another example, {"ufiw", "jufe", "eifd", "doer"} 

We will see that the last element of the first string is not similar to the first element of the second string, and also, the last element of the last string is not similar to the first element of the first string. Thus we can not form a circle using them. 

And if we look at another example, {“ehfc”, “jte”, “dpoij”, “ilasd”, “cji”}

The strings in the above example can be rearranged in the following order {"ehfc", "cji", "ilasd", "dpoij", "jte"}.

Then this array of strings can form a circle.

Now we need to devise a method to check if any given array of strings can form a circle or not. For this problem, We will be using a method based on eulerian circuits in directed graphs. 

So, let's first understand what your eulerian circuits are-

The eulerian circuit is a path in a graph that visits every node exactly once. It has the same vertex as its starting and ending point. Any graph that contains an eulerian circuit is known as an eulerian graph. 

We can check if a graph is an eulerian graph or not, with the help of the following conditions-

  • Every vertex has the same value of indegree and outdegree
  • All vertices with non zero degrees have to belong to a single strongly connected component

So we start with a graph having all 26 characters of the alphabet as nodes, then we form a directed graph by connecting each string's first and last character. Then we check if that graph is an eulerian graph or not. If the graph is eulerian, then the array of strings can form a circle, and if the graph is not an eulerian graph, the strings can not form a circle.

Algorithm for the solution

  • Create a graph with all 26 alphabets as nodes.
  • For each string, add an edge from the first character to the last character of the string.
  • Check if the formed graph is eulerian or not.
  • If it's eulerian return that the array of strings can form a circle, else return that they can not form a circle. 
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Implementation of the approach(C++)

#include <bits/stdc++.h>
#define chars 26
using namespace std;
//Class for the graph.
class graph
{
    int nofv;
    //Adjacency list to store the graph.
    list<int> *adjacencylist;
    int *in;
    public:
    //Constructor.
    graph(int nofv);
    //Destructor.
    ~graph()
    {
        delete [] adjacencylist;
        delete [] in;
    }
    //To add an edge to the graph.
    void addingedge(int edgestart, int edgeend)
    {
        adjacencylist[edgestart].push_back(edgeend);
        (in[edgeend])++;
    }
    //To check if a graph is eulerian or not.
    bool checkforeuleriancycle();
    //To check is a graph is strongly connected or not.
    bool checkforstronglyconnected();
    //Function for DFS of a graph.
    void fordfs(int startedge, bool marked[]);
    graph gettranspose();
};
//To create a graph.
graph::graph(int nofv)
{
    this->nofv=nofv;
    adjacencylist = new list<int>[nofv];
    in = new int[nofv];
    for(int i=0;i<nofv;i++)
    {
        in[i]=0;
    }
}
bool graph::checkforeuleriancycle()
{
    //If all non-zero degree vertices are connected.
    if(checkforstronglyconnected()==false)
    {
        return false;
    }
    //Checking if in degree and out degree is same or not.
    for(int i=0;i<nofv;i++)
    {
        if(adjacencylist[i].size()!=in[i])
        {
            return false;
        }
    }
    return true;
}
void graph::fordfs(int startedge, bool marked[])
{
    //To keep track of visited nodes.
    marked[startedge]=true;
    list<int>:: iterator itr;
    //Recursive call for adjacent vertices.
    for( itr=adjacencylist[startedge].begin();itr!=adjacencylist[startedge].end();++itr)
    {
        if(!marked[*itr])
        {
            fordfs(*itr, marked);
        }
    }
}
graph graph::gettranspose()
{
    graph G(nofv);
    for(int startedge=0;startedge<nofv;startedge++)
    {
        list<int>::iterator itr;         for(itr=adjacencylist[startedge].begin();itr!=adjacencylist[startedge].end();++itr)
        {
            //Creating the transpose of the graph.
            G.adjacencylist[*itr].push_back(startedge);
            (G.in[startedge])++;
        }
    }
    return G;
}
//To check if all non-zero degree vertices are strongly connected //or not.
bool graph::checkforstronglyconnected()
{
    //Create an array to keep track of visited nodes.
    bool marked[nofv];
    for(int i=0;i<nofv;i++)
    {
        marked[i]=false;
    }
    //Get first non-zero degree vertex.
    int n;
    for(n=0;n<nofv;n++)
    {
        if(adjacencylist[n].size()>0)
        {
            break;
        }
    }
    //Start DFS with that vertex.
    fordfs(n, marked);
    for(int i=0;i<nofv;i++)
    {
        //If DFS doesn't visit all the vertices, return false.
        if(adjacencylist[i].size()>0 && marked[i]==false)
        {
            return false;
        }
    }
    //Create transpose of the graph.
    graph Gr=gettranspose();
    for(int i=0;i<nofv;i++)
    {
        marked[i]=false;
    }
    //DFS of the transpose of the graph.
    Gr.fordfs(n, marked);
    //If it does not visit all the vertices, return false.
    for(int i=0;i<nofv;i++)
    {
        if(adjacencylist[i].size()>0 && marked[i]==false)
        {
            return false;
        }
    }
    return true;
}
//To check if the array of strings can form a circle or not.
bool circleformed(string str[], int n)
{
    //Create a graph with every character of alphabet as its
    //vertex.
    graph g(chars);
    //For every string create an edge from first to last
    //character of the string.
    for(int i=0;i<n;i++)
    {
        string s = str[i];
        g.addingedge(s[0]-'a', s[s.length()-1]-'a');
    }
    //Check if the graph formed is eulerian or not.
    //If it is eulerian, then it can form a circle, otherwise no.
    return g.checkforeuleriancycle();
}
int main()
{
    //Take no. of strings, and strings as user input.
    int n;
    cout<<"Enter the number of strings in the array, then elements ";
    cin>>n;
    string arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    //Function call to check if it can form the circle or not.
    int X=circleformed(arr, n);
    //Printing the result.
    if(X==1)
    {
        cout<<"The array of strings can form a circle. ";
    }
    else
    {
        cout<<"The array of strings can not form a circle. ";
    }
    return 0;
}

 

Input-

4
alsdf fkdjdhl lyywef fwera

 

Output-

Enter the number of strings in the array, then elements 
The array of strings can form a circle.

Complexity Analysis

Time Complexity: For each of 26 vertexes we traverse n edges (n=number of strings), so the overall complexity is O(n)

Space Complexity:O(n).

Frequently Asked Questions

  1. What is a circuit in a graph?
    A circuit is a path in a graph that starts and ends on the same vertex. 
     
  2. What is an eulerian circuit in a graph?
    A path in a graph contains each edge exactly once and has the same vertex as the start and endpoint.
     
  3. How is a path different from a circuit in the graph?
    A path in a graph is any route formed by the edges, whereas a circuit is a path that starts and ends from the same vertex.
     
  4. What do you mean by the adjacency matrix of a graph?
    It is a way of representing a finite graph. In it, we create a matrix by indexing rows and columns with the identical ordering of vertices. Then put one if there is an edge between the vertices at the row and column, else 0.
     
  5. What is a cycle in a graph?
    A cycle in a graph is a non-empty trail in a graph, with only identical first and last vertex. 

Key takeaways

In this blog, we learned the solution to the problem in which we are given an array of strings and asked to check if they can form a circle-

We started with creating a graph With 26 characters of the alphabet as its vertices. Then we go through the array of Strings, and for every string, we draw an edge between its first and last characters. Now we check if this graph is an eulerian graph or not with the following conditions-

The indegree and outdegree for each vertex are the same.

All vertices with a non-zero degree must belong to a single strongly connected component.

If both the conditions are true, the graph is an eulerian graph. Else, it is not an eulerian graph.

Now, if the graph is an eulerian graph, the array of strings can form a circle, else they can not form a circle.

Recommended problems -

 

You can read more about strings here and practice similar problems on code studio as well.

Previous article
k’th Heaviest Adjacent Node in a Graph where Each Vertex has Weight
Next article
Number of distinct Shortest Paths from Node 1 to N in a Weighted and Directed Graph
Live masterclass