Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 🥳
2.
Problem Statement 🧾
3.
Examples
4.
Approach
4.1.
Algorithm
4.2.
Example
4.3.
Implementation in C++
4.3.1.
Output
4.3.2.
Time Complexity ⌛
4.3.3.
Space Complexity 🚀
5.
Frequently Asked Questions
5.1.
What is a string array?
5.2.
What is a connected graph?
5.3.
Which data structure is used for DFS traversal?
5.4.
What are indegree and outdegree?
5.5.
What is the time complexity of DFS traversal?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if an Array of Strings can be Chained to Form a Circle

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

Introduction 🥳

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.   

Introduction

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. 

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. 

Input: 

Arr[] = { “DEER”, “RAIN”, “NIGHT”, “TRUCK”, “KID”}

String to cycle

Explanation: 

  • As “DEER” ends with “R” & “RAIN” starts with “R”. 
  • “RAIN” ends with “N” & “NIGHT” starts with “N”. 
  • “NIGHT” ends with “T” & “TRUCK” starts with “T”. 
  • “TRUCK” ends with “K” & “KID” starts with “K”. 
  • “KID” ends with “D” & “DEER” starts with “D”.
  • So the string array will form a circle. 
     

Output: Yes, They can form a circle 

Approach

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:

  1. The in and out-degree of each vertex are the same. 
  2. The graph is a connected graph.  

Algorithm

  1. Take string array as input from the user.
     
  2. Call function “canBeChained(array)”. Inside this function, do the following:
    1. Create a 2D vector to store the edges of the graph.
    2. Create two vectors to store the indegree and outdegree of the vertex.
    3. Create another vector to store if the character is visited or not.
    4. Count the indegree and outdegree for each vertex.
    5. For each character, compare if in and out-degree is different, then return false.
    6. Otherwise, check for the second condition, i.e., the graph is connected or not.
    7. Call function “isConnected()” to check this condition.
       
  3. In the “isConnected()” function, perform the following operations:
    1. Create a vector to pass it by reference in recursive DFS traversal
    2. Call the DFS function.
    3. Check if all vertices are visited; if no, return false.
       
  4. 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: 

Array of strings

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

The edges vector will be - 

Edge vector 

The above numbers are indexed according to the alphabetical order of the characters like 0 for A1 for B2 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).

DFS 1 

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

DFS 2

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

DFS 3

The next node to be visited is 24(Y)

DFS 4

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

DFS 5

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

output

Time Complexity ⌛

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 🚀

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.

 

Check out this problem - Longest Common Prefix

Frequently Asked Questions

What is a string array?

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

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. And also, enroll in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations. Nevertheless, you may consider our paid courses to give your career an edge over others!

Happy Coding

Previous article
Count the Number of Trees in a Forest
Next article
Check if a Graph is Strongly Connected
Live masterclass