An array of strings is an array with a fixed number of strings. An array of strings is called a string array. A string is a collection of a sequence of characters. These characters are stored in contiguous memory locations.

This blog will discuss a simple DSA problem related to arrays of strings. The problem is to check if an array of strings can be chained to form a circle.

Problem Statement 🧾

The problem is "Check if an array of strings can be chained to form a circle". This problem states that you are given a collection of a few strings stored in an array. Our task is to rearrange the strings. Then we have to check if it is possible to group these strings as a circle.

The condition for putting two strings together in a circle is - if the last character of the first string matches with the first character of the second string or vice versa.

Let's understand with an example.

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

Examples

Let us discuss the above problem with an example taken below.

The approach is to create a directed graph. Add an edge from 1st to the last character in the directed graph for each string in the given array. Now we need to find if an Eulerian cycle will be formed in the graph or not. If the graph forms an eulerian circuit, then the array can be chained to form a circle; otherwise, not. An Eulerian cycle is formed if and only if:

The in and out-degree of each vertex are the same.

The graph is a connected graph.

Algorithm

Take string array as input from the user.

Call function “canBeChained(array)”. Inside this function, do the following:

Create a 2D vector to store the edges of the graph.

Create two vectors to store the indegree and outdegree of the vertex.

Create another vector to store if the character is visited or not.

Count the indegree and outdegree for each vertex.

For each character, compare if in and out-degree is different, then return false.

Otherwise, check for the second condition, i.e., the graph is connected or not.

Call function “isConnected()” to check this condition.

In the “isConnected()” function, perform the following operations:

Create a vector to pass it by reference in recursive DFS traversal.

Call the DFS function.

Check if all vertices are visited; if no, return false.

Return true if all the conditions mentioned above are not satisfied.

Example

Let's now discuss working through an example, and then we will code it:

Step 1: Here we have to find the indegree and outdegree of each character.

The edges vector will be -

The above numbers are indexed according to the alphabetical order of the characters like 0 for A, 1 for B, 2 for C, and so on.

And for the above array in and outdegree will be as follows:

Character

INDEGREE

OUTDEGREE

E

1

1

H

1

1

R

1

1

T

1

1

Y

1

1

The in and out-degree for the remaining characters is zero.

Step 2: Check if indegree == outdegree for all characters. As from the above table, this condition is true.

So now we will check if the graph is connected or not.

Step 3: Run the DFS Algorithm. Taking the start node = ‘arr[0][0]’ = 7(h).

As 19 is in the stack so next we will visit node 19.

The next node in the stack is 4(E), so visit node 4.

The next node to be visited is 24(Y)

The next node to be visited is 17(R), which is present in the stack.

All the vertex are visited now, and hence the graph is connected.

Step 4: As DFS function will return true. So, print “Yes, They can form a circle” as output.

Let's now see the implementation to check if an array of strings can be chained to form a circle.

Implementation in C++

// C++ program to check if an array of strings can be chained to form a circle
#include<bits/stdc++.h>
using namespace std;
// Recursive approach for DFS
void DFS(vector<vector<int>>edges, vector<bool>& visited, int x){
visited[x] = true;
for(int i = 0; i < edges[x].size(); i++)
{
if(!visited[edges[x][i]])
{
DFS(edges, visited, edges[x][i]);
}
}
}
// Function to check if graph is connected.
bool isConnected(vector<vector<int>>edges, vector<bool> visitedVertex, int x)
{
vector<bool> visited(26);
// Call DFS function
DFS(edges, visited, x);
for(int i = 0; i < 26; i++)
{
if(visitedVertex[i] && !visited[i])
{
return false;
}
}
return true;
}
bool canBeChained(vector<string>arr)
{
// Creating 2d vector to store the edges.
vector<vector<int>> edges(26);
// Create two vectors for storing indegree and outdegree.
vector<int> in(26), out(26);
// Create a vector to store visited chrachter.
vector<bool> visited(26);
int n = arr.size(), first, last;
// Run loop to count the indegree and outdegree of strings.
for(int i = 0; i < n; i++)
{
first = arr[i][0] - 'a';
last = arr[i][arr[i].size() - 1] - 'a';
visited[first] = true;
visited[last] = true;
in[last]++;
out[first]++;
edges[first].push_back(last);
}
// Check if indegree and outdegree is same or not.
for(int i = 0; i < 26; i++)
{
if(in[i] != out[i])
{
return false;
}
}
// To check 2nd condition.
// i.e., Graph is connected or not.
return isConnected(edges, visited, arr[0][0] - 'a');
}
int main()
{
int n;
cout<<"Enter no. of strings : ";
cin>>n;
vector<string>arr;
cout<<"Enter "<<n<<" strings : \n";
for(int i=0;i<n;i++)
{
string s;
cin>>s;
arr.push_back(s);
}
if(canBeChained(arr))
cout << "Yes, They can form a circle " << endl;
else
cout << "No, circle cannot be formed" << endl;
return 0;
}

Output

Time Complexity ⌛

The time complexity of the problem "Check if an array of strings can be chained to form a circle" using the above approach is O(N+E), where N and E is the number of nodes and edges.

Space Complexity 🚀

The space complexity of the problem "Check if an array of strings can be chained to form a circle" using the above approach is O(N) for an array of the string of size N.

An array of strings is an array with a fixed number of strings. An array of strings is also called a string array.

What is a connected graph?

If there exists a path from every one vertex to every other vertex, i.e., between each pair of vertices. Then the graph is a connected graph.

Which data structure is used for DFS traversal?

The stack data structure is used for DFS(Depth First Search) traversal.

What are indegree and outdegree?

Indegree is the number of edges coming toward the vertex. Outdegree is the number of edges going away from the vertex.

What is the time complexity of DFS traversal?

The time complexity of DFS traversal is O(V+E). V and E are the numbers of vertex and edges.

Conclusion

In this article, we have discussed a coding problem in which we have to check if an array of strings can be chained to form a circle. We have seen the question's solution, time, and space complexity(Check if an array of strings can be chained to form a circle).

If you found this blog has helped you enhance your knowledge about the above question, and if you want to learn more, check out our articles