Ninja And Alien

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:

1. 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.
2. Now, apply the topological sort in the created graph in order to find the required order.
3. 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:

1. Define a map let’s say “degree”.
2. Define another map let’s say “graph”.
3. 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
4. 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
5. “result” := Initialise a blank string to store the final order
6. Initialise a queue “que”
7. 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”
8. Now, while (not “que” is empty), do −
   1. x := first element of “que”
   2. delete element from “que”
   3. result := result + x
   4. 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)
9. 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: 

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

O(N + W), where ‘N’ is the number of words in the array, and ‘W’ is the size of words.

The time complexity of topological sorting is O(V + E), where ‘V’ is the number of vertices and ‘E’ is the number of edges, because in the worst case the algorithm will traverse through the complete graph, that is V vertices and E - 1 edges. So, the time complexity is O(N + W).

O(N), where ‘N’ is the number of words in the array

Extra space required for data structures used like queue and maps. So, space complexity is O(N).