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), 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).

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).

'''

	Time complexity: O(N + W) 
	Space complexity: O(N)
	
	where 'N' is the number of words in the array, and 'W' is the size of words.

'''

from collections import defaultdict, deque 
import heapq

# Function to create graph
def constructGraph(words): 

    # Initialise a map to store the graph
    graph=defaultdict(set)
    
    # Create nodes
    for i in range(len(words)):
        for j in range(len(words[i])):

            # Store word in a variable
            c = words[i][j]

            # If word does not exist in the graph
            if (c not in graph): 

                # Create a temporary set
                temp=set()

                # Add the node
                graph[c] = temp

    for i in range(len(words)-1):

        # Initialise a variable to follow index
        index = 0

        # traverse until you reach end of one of the words
        while (index < len(words[i]) and index < len(words[i + 1])): 

            # If you find the mismatched character
            if (words[i][index] != words[i + 1][index]): 

                # add node into the graph
                graph[words[i][index]].add(words[i + 1][index])
                break

            # Increment index
            index+=1

        # Check if index is equal to smaller length from the two words
        if (index == min(len(words[i]), len(words[i + 1]))): 
            if (len(words[i]) > len(words[i + 1])): 

                # Return an empty map
                return set()

    # Return graph
    return graph


# Function to get indegree of element
def getIndegree(graph):

    # Initialise a map to store indegree
    indegree=defaultdict(int)

    # Traverse until iterator reaches end of graph
    for iter in graph:

        # Update value
        indegree[iter] = 0


    # Traverse until iterator reaches end of graph
    for iter in graph: 

        # Initialise through the graph.
        for _iter in graph[iter]:

            # Update
            indegree[_iter] = indegree[_iter] + 1

    # Return the indegree map
    return indegree


#Function to find topological ordering    
def topologicalSorting(graph): 

    # initialise another map to store degree
    indegree = getIndegree(graph)

    # Initialise priority queue instead of simple queue in order to create lexicographical order
    que=[]
    heapq.heapify(que)

    # Initialise an iterator to traverse through map
    for iter in indegree:

        # If degree = 0
        if (indegree[iter] == 0):

            # Push value into the queue
            heapq.heappush(que,iter)


    # initialise a string to store the order
    result = ""

    # while queue is not empty
    while (len(que)>0): 

        # Store top element of queue 
        head = heapq.heappop(que);

        result += head;

        # Start iterator from head of graph's begin
        for iter in graph[head]:

            # Store iterator pointer as neighbor
            neighbor = iter

            # Update indegree of neighbor
            indegree[neighbor] -= 1

            # If now, the indegree of neighbor is zero
            if (indegree[neighbor] == 0) :

                # Push neighbor into the queue
                heapq.heappush(que,neighbor)


    # check if length of string is not equal to size of indegree     
    if (len(result) != len(indegree)):

        # return an empty string
        return ""

    # else return the order 
    return result

def alienOrder(words, n):

    # initialise unordered_map to store the graph
    graph = constructGraph(words)
    
    # If graph is empty return an empty string
    if (len(graph)==0):
        return ""

    # return the topological order of the graph
    return topologicalSorting(graph)

    

/*

	Time complexity: O(N + W) 
	Space complexity: O(N)
	
	where 'N' is the number of words in the array, and 'W' is the size of words.

*/

#include
#include
#include
#include
#include


// function to create graph
unordered_map > constructGraph(vector& words) 
{

    // initialise a map to store the graph
    unordered_map > graph;
    
    // create nodes
    for(int i = 0; i < words.size(); i++) 
    {
        for (int j = 0; j < words[i].size(); j++) 
        {

            // store word in a variable
            char c = words[i][j];

            // if word does not exist in the graph
            if (graph.find(c) == graph.end()) 
            {

                // create a temporary set
                set temp;

                // add the node
                graph[c] = temp;
            }
        }
    }
    for (int i = 0; i < words.size() - 1; i++) 
    {

        // initialise a variable to follow index
        int index = 0;

        // traverse until you reach end of one of the words
        while (index < words[i].size() && index < words[i + 1].size()) 
        {

            // if you find the mismatched character
            if (words[i][index] != words[i + 1][index]) 
            {

                // add node into the graph
                graph[words[i][index]].insert(words[i + 1][index]);
                break;
            }

            // increment index
            index++;
        }

        // check if index is equal to smaller length from the two words
        if (index == min(words[i].size(), words[i + 1].size())) 
        {
            if (words[i].size() > words[i + 1].size()) 
            {

                // return an empty map
                return unordered_map >();
            }
        }
    }

    // return graph
    return graph;
}


// function to get indegree of element
unordered_map getIndegree(unordered_map >& graph) 
{

    // initialise a map to store indegree
    unordered_map indegree;

    // initialise an iterator from start of graph
    unordered_map >::iterator iter;
    iter = graph.begin();

    // traverse until iterator reaches end of graph
    while (iter != graph.end()) 
    {

        // update value
        indegree[iter->first] = 0;

        // increment iterator
        iter++;
    }

    // start again from start of graph    
    iter = graph.begin();

    // traverse until iterator reaches end of graph
    while (iter != graph.end()) 
    {

        // initialise another iterator
        set::iterator _iter = (iter->second).begin();

        // while second iterator reaches end
        while (_iter != (iter->second).end()) 
        {

            // update
            indegree[*_iter] = indegree[*_iter] + 1;
            
            // increment second iterator
            _iter++;
        }

        // increment first iterator
        iter++;
    }

    //return the indegree map
    return indegree;
}


//function to find topological ordering    
string topologicalSorting(unordered_map > graph) 
{

    // initialise another map to store degree
    unordered_map indegree = getIndegree(graph);

    // initialise priority queue instead of simple queue in order to create lexicographical order
    priority_queue, greater > que;

    // initialise an iterator to traverse through map
    unordered_map::iterator iter;

    // start iterator from begin
    iter = indegree.begin();

    // while iterator reaches end do 
    while (iter != indegree.end()) 
    {

        // if degree = 0
        if (indegree[iter->first] == 0) 
        {

            // push value into the queue
            que.push(iter->first);
        }

        //increment iterator
        iter++;
    }

    // initialise a string to store the order
    string result = "";

    // while queue is not empty
    while (que.size()) 
    {

        // store top element of queue 
        char head = que.top();

        // pop the top element
        que.pop();

        // append head of queue into the result
        result += head;

        // initialise an iterator of set
        set::iterator iter;

        // start iterator from head of graph's begin
        iter = graph[head].begin();

        // while iterator reaches end
        while (iter != graph[head].end()) 
        {

            // store iterator pointer as neighbor
            char neighbor = *iter;

            // update indegree of neighbor
            indegree[neighbor] -= 1;

            // if now, the indegree of neighbor is zero
            if (indegree[neighbor] == 0) 
            {

                // push neighbor into the queue
                que.push(neighbor);
            }

            // increment iterator
            iter++;
        }
    }

    // check if length of string is not equal to size of indegree     
    if (result.size() != indegree.size()) 
    {

        // return an empty string
        return "";
    }

    // else return the order 
    return result;
}

string alienOrder(vector &words, int n)
{

    // initialise unordered_map to store the graph
    unordered_map > graph = constructGraph(words);
    
    // If graph is empty return an empty string
    if (!graph.size()) 
    {
        return "";
    }

    // return the topological order of the graph
    return topologicalSorting(graph);
}

    

/*

	Time complexity: O(N + W) 
	Space complexity: O(N)
	
	where 'N' is the number of words in the array, and 'W' is the size of words.

*/

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Collections;

public class Solution 
{
	// function to create graph
	private static HashMap> constructGraph(ArrayList words) 
	{

		// initialise a HashMap to store the graph
		HashMap> graph = new HashMap>();

		// create nodes
		for (int i = 0; i < words.size(); i++) 
		{
			for (int j = 0; j < words.get(i).length(); j++) 
			{

				// store word in a variable
				Character c = words.get(i).charAt(j);

				// if word does not exist in the graph
				if (!graph.containsKey(c)) 
				{

					// create a temporary HashSet
					HashSet temp = new HashSet();

					// add the node
					graph.put(c, temp);
				}
			}
		}
		for (int i = 0; i < words.size() - 1; i++) 
		{

			// initialise a variable to follow index
			int index = 0;

			// traverse until you reach end of one of the words
			while (index < words.get(i).length() && index < words.get(i + 1).length()) 
			{

				// if you find the mismatched character
				if (words.get(i).charAt(index) != words.get(i + 1).charAt(index)) 
				{

					// add node into the graph
					char a = words.get(i).charAt(index);
					char b = words.get(i + 1).charAt(index);
					graph.get(a).add(b);
					break;
				}

				// increment index
				index++;
			}

			// check if index is equal to smaller length from the two words
			if (index == Math.min(words.get(i).length(), words.get(i + 1).length())) 
			{
				if (words.get(i).length() > words.get(i + 1).length()) 
				{
					// return an empty HashMap
					return new HashMap>();
				}
			}
		}

		// return graph
		return graph;
	}

	// function to get indegree of element
	private static HashMap getIndegree(HashMap> graph) 
	{

		// initialise a HashMap to store indegree
		HashMap indegree = new HashMap();

		// initialise an iterator from start of graph
		Iterator>> iter = graph.entrySet().iterator();

		// traverse until iterator reaches end of graph
		while (iter.hasNext()) 
		{
			Map.Entry> entry = iter.next();
			// update value
			indegree.put(entry.getKey(), 0);
		}

		// start again from start of graph
		iter = graph.entrySet().iterator();

		// traverse until iterator reaches end of graph
		while (iter.hasNext()) 
		{

			// initialise another iterator
			Map.Entry> entry = iter.next();
			Iterator _iter = (entry.getValue()).iterator();

			// while second iterator reaches end
			while (_iter.hasNext()) 
			{

				// update
				char cur = _iter.next();
				indegree.put(cur, indegree.get(cur) + 1);

			}
		}

		// return the indegree map
		return indegree;
	}

	// function to find topological ordering
	private static String topologicalSorting(HashMap> graph) 
	{

		// initialise another HashMap to store degree
		HashMap indegree = getIndegree(graph);

		// initialise priority queue instead of simple queue in order to create
		// lexicographical order

		PriorityQueue que = new PriorityQueue<>();

		// initialise an iterator to traverse through map
		// start iterator from begin
		Iterator> iter = indegree.entrySet().iterator();

		// while iterator reaches end do
		while (iter.hasNext()) 
		{

			Map.Entry entry = iter.next();
			// if degree = 0
			if (entry.getValue() == 0) 
			{

				// push value into the queue
				que.add(entry.getKey());
			}
		}

		// to store the order
		StringBuilder result = new StringBuilder();

		// while queue is not empty
		while (!que.isEmpty()) 
		{

			// store top element of queue
			char head = que.remove();

			// append head of queue into the result
			result.append(head);

			// initialise an iterator of set
			Iterator _iter = (graph.get(head)).iterator();

			// while iterator reaches end
			while (_iter.hasNext()) 
			{

				// store iterator pointer as neighbor
				char neighbor = _iter.next();

				// update indegree of neighbor
				indegree.put(neighbor, indegree.get(neighbor) - 1);

				// if now, the indegree of neighbor is zero
				if (indegree.get(neighbor) == 0) 
				{

					// push neighbor into the queue
					que.add(neighbor);
				}

			}
		}

		// check if length of string is not equal to size of indegree
		if (result.length() != indegree.size()) 
		{

			// return an empty string
			return "";
		}

		// else return the order
		return result.toString();
	}

	public static String alienOrder(ArrayList words, int n) 
	{

		// initialise HashMap to store the graph
		HashMap> graph = constructGraph(words);

		// If graph is empty return an empty string
		if (graph.isEmpty()) 
		{
			return "";
		}

		// return the topological order of the graph
		return topologicalSorting(graph);
	}

}