Last Updated: 20 Feb, 2021

Ninja And Alien

Hard

Asked in companies

Solve now

Problem statement

An alien spaceship arrived at our planet Earth. An alien dropped his dictionary of words on the way back to his planet. Ninja found that dictionary and now wants to create the order of the characters of that language. Help ninja in creating the order of the characters with the help of the list of words given as were found in the Alien’s dictionary.

Example:

Let us assume that we have a list of words found in the dictionary in the same order as given: [“baa”, “abcd”, “abca”, “cab”, “cad”]

Now, ninja needs to find the order of the characters used in these strings.

The order would be: ‘b’, ‘d’, ‘a’, ‘c’, because “baa” comes before “abcd”, hence ‘b’ will come before ‘a’ in the order, similarly because, “abcd” comes before “abca”, ‘d’ will come before ‘a’. And so on.

Note:

A certain list of words might have more than one correct order of characters. In such cases, you need to find the smallest in normal lexicographical order. In the case of INVALID ORDER, simply return an empty string.

Invalid Order:

words = [“aba”, “bba”, “aaa”]. 
In this case, no valid order is possible because, from the first two words, we can deduce ‘a’ should appear before ‘b’, but from the last two words, we can deduce ‘b’ should appear before ‘a’ which is not possible.

More than one correct order:

words = [“ca”, “cb”]. 
In this case, we only know that ‘b’ will come after ‘a’ in the order of characters, but we don't have any knowledge of ‘c’. So, the valid correct orders can be = “abc”, “cab”, “acb”. Out of these, “abc” is lexicographically smallest, hence it will be printed.

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain an integer ‘N’, which denotes the number of words in the dictionary.

The second line of each test case will contain ‘N’ space-separated strings which denote the words of the dictionary.

Output Format:

For each test case, print the order of characters.

Output for every test case will be printed in a separate line.

Constraints:

1 <= T <= 10
1 <= N <= 300
0 <= size <= 100

Time limit: 1 sec

Solve now

Approaches

01 Approach

The idea behind this approach is to create a graph of the words of the dictionary and then apply the topological ordering of the graph.

A topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge u v from vertex u to vertex v, u comes before v in the ordering.

The approach is to take two words from the array of words and then compare characters of both words and find the first character that is not the same in the words.

Then, create an edge in the graph from the first different character of the first word to the second word.

Finally, apply topological sorting in the above-created graph.

Let us understand this better by dividing the complete solution into two parts:

Graph Creation:
We will use unordered_map to store the graph. The graph will be created by using below steps:
We’ll start with two words, let’s say a and b. Now we find the smaller word from the two, so that we could just traverse to that position.
Let’s say a has 3 characters and b has 5 characters. Now in order to find the first mismatched character we traverse from start to the length of the smaller word and check each character, until we find the first mismatched character.
Now, we simply create an edge between the first mismatched character of the first word to the second word.
Continue this process until all the edges are created.
Now, we will have a graph created with 1st mismatched character from each word to the other.
Now, apply the topological sort in the created graph in order to find the required order.
Topological Sorting:
The topological sorting algorithm is used in directed graphs(like the one we created), in which we need to find an order of edges such that every edge leads from the vertex of a smaller value assigned to the larger value. To read more about topological sorting you can refer: https://cp-algorithms.com/graph/topological-sort.html
Basically, we start from a vertex let’s say v and run along all edges that are outgoing from the same. This will not move along the edges for which the destination vertex has already been visited.
Continue the same process from the rest of the edges and then start from them,
By the end of this method, all vertices would be reached from the starting vertex v either directly or indirectly.
Finally, we will use a queue to store the topological order of all vertices.

Algorithm + Pseudo Code:

Define a map let’s say “degree”.
Define another map let’s say “graph”.
Now initialize i from i = 0 to i < size of words, while updating i by one in each traversal and, do −
Initialize another var j from j = 0 to j < size of words, while updating j by one in each traversal and, do −
degree[words[i, j]] := 0
Next initialize i from i = 0 to i < (size of words - 1), while updating i by one in each traversal and, do −
Initialise a var “mini” := minimum of size of words[i] and size of words[i + 1]. In order to find the smaller word, we could traverse only to that value.
Initialise j from j = 0 to j < mini, while updating j by one in each traversal and, do −
Store in a var x := words[i, j]
Store in a var y := words[i + 1, j]
If x is not equal to y, then − (First different character found)
insert y at the end of “graph[x]”
(increase degree[y] by 1)
Come out from the loop
“result” := Initialise a blank string to store the final order
Initialise a queue “que”
For each key-value pair let’s say “iter” in “degree”, do −
if value of “iter” is same as 0, then −
insert key of it into “que”
Now, while (not “que” is empty), do −
x := first element of “que”
delete element from “que”
result := result + x
for every element let’s say “elem” in “graph” do −
decrease degree[elem] by 1
Now, if degree[elem] is same as 0, then −
insert “elem” into “que”
(increase “elem” by 1)
return (if size of “result” is same as the size of “degree”, then result, otherwise return a blank string)

Keep in mind the following cases:

The longer string with the same prefix comes first, will make it an invalid case.
In case of more than one correct order, simply return the lexicographical smallest order.

Solve now