Find if an Array of Strings can be Chained to form a Circle in Java

Find whether an array of strings may be linked together to create a circle. If the last character of string X and the first character of string Y are the same, then string X can be positioned in a circle before string Y.

Example 1:

Input:

String a = {"python", "nodejs", "scripted-php"}

Output:

Yes, the strings can be chained to form a circle.

Explanation:

For the given array of strings, the strings that can be formed as chains are python ? nodejs; nodejs ? scripted-php; scripted-php ? python. Hence, the strings can be chained to form a circle.

Example 2:

Input:

String a = {"bac", "cda", "aaa", "aab"}

Output:

Yes, the strings can be chained to form a circle.

Explanation:

For the given array of strings, the strings that can be formed as chains are bac ? cda; cda ? aaa; aaa ? aab; aab ? bac. Hence, the strings can be chained to form a circle.

Example 3:

Input:

String a = {"ijk", "kji", "abc", "cba"}

Output:

No, the strings cannot be chained to form a circle.

Explanation:

For the given array of strings, the strings that can be formed as chains are ijk ? kji; abc ? cba, but they cannot be formed as a cycle. Hence, the strings cannot be chained to form a circle.

Approach: Using Directed Graphs

The approach implements into practice an algorithm to determine if a directed graph can form an Eulerian cycle. It accomplishes this by verifying two conditions:

Strong Connectivity (isSC): It determines if every vertex in the network that has a degree greater than zero is strongly connected, indicating that every vertex can be accessed from every other vertex.

Equivalent in terms of both in and out degrees: It checks if each vertex's in-degree and out-degree are equal, which is an essential requirement for Eulerian cycles.

The technique iterates over the graph using depth-first search (DFS), verifying that all vertices have been visited. In order to verify the connection in both directions, the graph is also constructed in reverse. In the final step, it makes use of the graph structure to determine if the given collection of strings may be chained together to form an Eulerian cycle.

Algorithm:

Step 1: Declare a class called StringChainedCycle.to represent an undirected graph.

Step 2: Initialize the class variables with the following values: "in" indicates an array to store the in-degree of each vertex; "ver" indicates the total number of vertices; and "adj" indicates a dynamic array of adjacency lists to store the graph structure.

Step 3: Set up each vertex's adjacency lists and class variables.

Step 4: Update the destination vertex in in-degree and add an edge connecting two vertices in the graph.

Step 5: Check each vertex's degree and connection to see if the network has an Eulerian cycle.

Step 6: Use Depth First Search (DFS) to confirm that there is strong connectivity between vertices of non-zero degrees.

Step 7: Start with the Depth First Search traversal, beginning at a specified vertex.

Step 8: To verify the connection, obtain the graph's transposition (reverse).

Step 9: Apply an array of strings as a basis, and create a graph in which each string represents an edge.

Step 10: Return true to indicate that the strings can be linked together if the graph contains an Eulerian cycle.

Implementation:

FileName: StringChainedCycle.java

Output:

Yes, it can be chained 

Complexity Analysis:

The time complexity of the above code is O(N), and the space complexity is O(N).