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

Examples

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

Input: 

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

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: 

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.

 

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

• Balanced Binary Search Trees 
• Rabin Karp Algorithm
• Check if an array represents inorder of BST
• Longest common prefix from suffix array
• Detect cycle in directed graph
   

Recommended problems -

• Maximum sum subarray of size k
• Max circular subarray sum
• Subarray sums divisible by k
• Shortest subarray with sum at least k

 

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