Problem Statement

Given a sorted dictionary of an alien language having N words and K alphabets of a standard dictionary. Find the order of characters in the alien language. There may be multiple valid orders for a particular test case, thus you may return any valid order. The output will be True if the order returned by the function is correct, else False denoting an incorrect order.

Examples

Example 1:

Input: N = 5, K = 5,
       dict = [
                "baa",
                "abcd",
                "abca",
                "cab",
                "cad"
               ]
Output: b d a c

Explanation:
The pair "baa" and "abcd" suggests 'b' appears before 'a' in the alien dictionary.
The pair "abcd" and "abca" suggests 'd' appears before 'a' in the alien dictionary.
The pair "abca" and "cab" suggests 'a' appears before 'c' in the alien dictionary.
The pair "cab" and "cad" suggests 'b' appears before 'd' in the alien dictionary.

So, ['b', 'd', 'a', 'c'] is a valid ordering.

Example 2:

Input: N = 3, K = 3
       dict = [
               "caa",
               "aaa",
               "aab"
              ]
Output: c a b

Different Approaches

1️⃣ Topological Order (BFS)

Intuition:

How this problem can be identified as a Graph problem?

The problem suggests that there exists the ordering of different words based on the alien dictionary. Also, it is asked to find out the ordering of letters based on the dictionary. The concept of ordering of nodes can be solved using Topological sort which comes under the topic of Graphs.
How to form the graph?
Here, the letters can be represented as nodes of the graph.

To understand the edges, consider example 1 where
N=5, K=4, dict = {"baa", "abcd", "abca", "cab", "cad"}

Considering the first two words "baa" and "abcd", it is clear that they are differentiated by the first letter i.e. 'b' and 'a'. Thus, a directed edge can be inserted in the graph from node 'b' to node 'a' representing that letter 'b' must appear before the letter 'a' in the ordering as shown in the figure:

By comparing pairs of words in the dictionary, edges can be added to the graph.

Note:

It is not required to check every pair of words possible to add the edges to the graph. Instead just checking the differentiating letter in consecutive pairs will work as well as shown in the image:

Edge Case:

The problem arises when the value of K becomes 5 and there is no word in the dictionary containing the letter 'e'. In this case, a separate node with the value 'e' can be added in the graph and it will be considered a component of the directed graph like the following, and the same algorithm will work fine for multiple components.

Approach:

1. Initialize a graph with nodes equal to the number of required letters. The letters from 'a' to 'z' can be represented as numbers from 0 to 26 for easier understanding.
2. Compare the consecutive pair of words, and find the differentiating letter. Compare the letters to add an edge to the graph.
3. Once the graph is prepared, get the topological ordering of the graph formed.
4. The ordering of letters obtained from the topological sorting, will be the ordering of letters based on the alien dictionary.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:

    /* Function to return the topological
     sorting of given graph */
    vector<int> topoSort(int V, vector<int> adj[]) {
	    
        // To store the In-degrees of nodes
	    vector<int> inDegree(V, 0);
	    
	    // Update the in-degrees of nodes
		for (int i = 0; i < V; i++) {
		    
			for(auto it : adj[i]) {
			    // Update the in-degree
			    inDegree[it]++;
			}
		}
        
        // To store the result
        vector<int> ans;
	    
	    // Queue to facilitate BFS
	    queue<int> q;
	    
	    // Add the nodes with no in-degree to queue
	    for(int i=0; i<V; i++) {
	        if(inDegree[i] == 0) q.push(i);
	    }
	    
	    // Until the queue is empty
	    while(!q.empty()) {
	        
	        // Get the node
	        int node = q.front();
	        
	        // Add it to the answer
	        ans.push_back(node);
	        q.pop();
	        
	        // Traverse the neighbours
	        for(auto it : adj[node]) {
	            
	            // Decrement the in-degree
	            inDegree[it]--;
	            
	            /* Add the node to queue if 
	            its in-degree becomes zero */
	            if(inDegree[it] == 0) q.push(it);
	        }
	    }
	    
	    // Return the result
	    return ans;
    }
    
public:

	/* Function to determine order of 
	letters based on alien dictionary */
	string findOrder(string dict[], int N, int K) {
		
		// Initialise a graph of K nodes
		vector<int> adj[K];
		
		// Compare the consecutive words
		for(int i=0; i < N-1; i++) {
		    
		    string s1 = dict[i];
			string s2 = dict[i + 1];
			int len = min(s1.size(), s2.size());
			
			/* Compare the pair of strings letter by 
			letter to identify the differentiating letter */
			for (int ptr = 0; ptr < len; ptr++) {
			    
			    // If the differentiating letter is found
				if (s1[ptr] != s2[ptr]) {
				    
				    // Add the edge to the graph
					adj[s1[ptr] - 'a'].push_back(s2[ptr] - 'a');
					break;
				}
			}
		}
		
		/* Get the topological sort 
		of the graph formed */
		vector<int> topo = topoSort(K, adj);
		
		// To store the answer
		string ans;
		
        for(int i=0; i < K; i++) {
            // Add the letter to the result
            ans.push_back('a' + topo[i]);
            ans.push_back(' ');
        }
		
		// Return the answer
		return ans;
	}
};

int main() {
    
    int N = 5, K = 4;
    string dict[N] = {
        "baa","abcd","abca","cab","cad"
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to determine order of 
	letters based on alien dictionary */
    string ans = sol.findOrder(dict, N, K);
    
    // Output
    cout << "The order to characters as per alien dictionary is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(K+N) (where K and N represents the number of nodes and edges in the given graph)
  • Forming the graph takes O(N*len) time, where len is the average length of a word in the dictionary.
  • Finding topological sort takes O(K+N) time.
• Space Complexity: O(K+N)
  • Storing the graph takes O(N) space.
  • Topological sorting algorithm uses extra O(K) computational space.