Circle of Words

Ninja
0/200
Average time to solve is 63m
profile
Contributed by
10 upvotes
Asked in companies
Urban Company (UrbanClap)SamsungGoogle inc

Problem statement

You are given an array/list of words, your task is to check whether the individual words can be rearranged to form a circle.

Two words, ‘X’ and ‘Y’, can be put together in a circle if the last character of ‘X’ is the same as the first character of ‘Y’ or vice versa.

For Example: 
For the array [ “TUNA”, “TIGER”, “RABBIT”, “RAT”, “ANTEATER” ],

A possible circle can be:

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains a single integer ‘N’, representing the size of the array.

The second line of each test case contains ‘N’ space-separated strings representing the words of the given array.
Output Format: 
For each test case print ‘true’ if you can make a circle by rearranging the given words, else print ‘false’.

Output for each test case will be printed in a separate line.
Note 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 100
1 <= N <= 10^5
1 <= L <= 20

Where L is the length of each word in the given array.

It is guaranteed that the sum of N over all test cases doesn’t exceed 10^5.

Time Limit: 1 sec.

Sample Input 1:

2
6
DONE LAST EQUAL TOSS SOME END
5
ROPE NONE RUN EAR EXPERIENCE

Sample Output 1:

true
false

Explanation For Sample Output 1:

For the first test case, the words can be rearranged as:

For the second test case, no possible way exists.

Sample Input 2:

2
4
NOW AGAIN WONDER GO
3
CHECK SYNC KEYS

Sample Output 2:

false
true
Hint

Try to convert the given problem into a directed graph problem.

Approaches (1)
Directed Graph

We will build a directed graph and for each word, we will add an edge from the first character to the last character in the graph. Now we just have to check whether the graph contains an Eulerian cycle or not. If it contains an Eulerian cycle, then we can form a circle.

 

The conditions for the existence of an Eulerian cycle in a directed graph are:

  1. Every node should have in - degree == out-degree.
  2. All the nodes belong to a single strongly connected component.
     

Eulerian Cycle: An Eulerian Cycle is a trail that starts and ends at the same graph vertex. In other words, it is a graph cycle that uses each graph edge exactly once.

You can learn more about Eulerian Cycle at the given link:

https://mathworld.wolfram.com/EulerianCycle.html

 

Algorithm: 

 

  1. dfs function:
    1. Create a ‘DFS’ function to traverse the graph.
    2. It will take the graph, current node, and a ‘VIS’ vector as arguments.
    3. It will traverse the tree recursively by calling the ‘DFS’ function for the child nodes which are not visited.
       
  2. check function:
    1. It will check whether the graph is fully traversed or not.
    2. It will take the graph and ‘VIS’ vector as arguments and check whether every existing node is visited or not.
       
  3. transpose function:
    1. It will transpose a given graph.
    2. It will take the graph and size of the graph as arguments and will reverse each edge and return the transposed graph.
       
  4. isStronglyConnected function:
    1. It will check whether all the nodes of the graph form a single strongly connected component or not.
    2. We will create a ‘VIS’ vector to store the information whether a node is already visited or not.
    3. Then we will call the ‘DFS’ function on the graph with an existing node.
    4. Then we will check whether the graph is fully traversed or not.
    5. If not, then we will return false.
    6. Now we will reinitialize the ‘VIS’ vector to false and make a transpose of the graph.
    7. Then again we will call the ‘DFS’ function on the transposed graph.
    8. And finally, we will check whether all the nodes are visited or not.
  5. Given function:
    1. We will create a vector of vectors to store the adjacency list and two vectors to store the in-degree and out-degree of each node.
    2. Then we will iterate over the words and for each word add an edge from the first character to the last character of the word.
    3. We will also count the in-degree and the out-degree of each node.
    4. Then we will check whether every node has the same in-degree and out-degree or not.
    5. And finally, we will check whether all the nodes form a single strongly connected component or not.
Time Complexity

O(N), where ‘N’ is the size of the array.

 

The time complexity will be similar to that of ‘dfs’ i.e O( V + E), where ‘V’ is the number of vertices and ‘E’ is the number of edges. In this problem, the maximum number of vertices can be 26, and the number of edges will be N. So the overall time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the size of the array.
 

We are taking three vectors, ‘vis’, ‘in’, ‘out’, of size ‘N’, and two graphs of size ‘N’.

So the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Circle of Words
Full screen
Console