Alien Dictionary

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:

Initialise 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.
Compare the consecutive pair of words, and find the differentiating letter. Compare the letters to add an edge to the graph.
Once the graph is prepared, get the topological ordering of the graph formed.
The ordering of letters obtained from the topological sorting, will be the ordering of letters based on the alien dictionary.

Dry Run:

Solution:

#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;
}
import java.util.*;

class Solution {
    
    /* Function to return the topological
     sorting of given graph */
    private List<Integer> topoSort(int V, List<Integer>[] adj) {
        
        // To store the In-degrees of nodes
        int[] inDegree = new int[V];
        
        // Update the in-degrees of nodes
        for (int i = 0; i < V; i++) {
            
            for (int it : adj[i]) {
                // Update the in-degree
                inDegree[it]++;
            }
        }
        
        // To store the result
        List<Integer> ans = new ArrayList<>();
        
        // Queue to facilitate BFS
        Queue<Integer> q = new LinkedList<>();
        
        // Add the nodes with no in-degree to queue
        for (int i = 0; i < V; i++) {
            if (inDegree[i] == 0) q.add(i);
        }
        
        // Until the queue is empty
        while (!q.isEmpty()) {
            
            // Get the node
            int node = q.poll();
            
            // Add it to the answer
            ans.add(node);
            
            // Traverse the neighbours
            for (int 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.add(it);
            }
        }
        
        // Return the result
        return ans;
    }
    
    /* Function to determine order of 
    letters based on alien dictionary */
    public String findOrder(String[] dict, int N, int K) {
        
        // Initialise a graph of K nodes
        List<Integer>[] adj = new ArrayList[K];
        for (int i = 0; i < K; i++) adj[i] = new ArrayList<>();
        
        // Compare the consecutive words
        for (int i = 0; i < N - 1; i++) {
            
            String s1 = dict[i];
            String s2 = dict[i + 1];
            int len = Math.min(s1.length(), s2.length());
            
            /* 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.charAt(ptr) != s2.charAt(ptr)) {
                    
                    // Add the edge to the graph
                    adj[s1.charAt(ptr) - 'a'].add(s2.charAt(ptr) - 'a');
                    break;
                }
            }
        }
        
        /* Get the topological sort 
        of the graph formed */
        List<Integer> topo = topoSort(K, adj);
        
        // To store the answer
        StringBuilder ans = new StringBuilder();
        
        for (int i = 0; i < K; i++) {
            // Add the letter to the result
            ans.append((char) ('a' + topo.get(i)));
            ans.append(' ');
        }
        
        // Return the answer
        return ans.toString();
    }
    
    public static void main(String[] args) {
        
        int N = 5, K = 4;
        String[] dict = {
            "baa", "abcd", "abca", "cab", "cad"
        };
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution();
        
        /* Function call to determine order of 
        letters based on alien dictionary */
        String ans = sol.findOrder(dict, N, K);
        
        // Output
        System.out.println("The order to characters as per alien dictionary is: " + ans);
    }
}
from collections import deque

class Solution:

    # Function to return the topological
    # sorting of given graph
    def topoSort(self, V, adj):
        
        # To store the In-degrees of nodes
        inDegree = [0] * V
        
        # Update the in-degrees of nodes
        for i in range(V):
            for it in adj[i]:
                # Update the in-degree
                inDegree[it] += 1

        # To store the result
        ans = []
        
        # Queue to facilitate BFS
        q = deque()
        
        # Add the nodes with no in-degree to queue
        for i in range(V):
            if inDegree[i] == 0:
                q.append(i)
        
        # Until the queue is empty
        while q:
            # Get the node
            node = q.popleft()
            
            # Add it to the answer
            ans.append(node)
            
            # Traverse the neighbours
            for it in adj[node]:
                # Decrement the in-degree
                inDegree[it] -= 1
                
                # Add the node to queue if its in-degree becomes zero
                if inDegree[it] == 0:
                    q.append(it)
        
        # Return the result
        return ans

    # Function to determine order of 
    # letters based on alien dictionary
    def findOrder(self, dict, N, K):
        
        # Initialise a graph of K nodes
        adj = [[] for _ in range(K)]
        
        # Compare the consecutive words
        for i in range(N - 1):
            
            s1 = dict[i]
            s2 = dict[i + 1]
            length = min(len(s1), len(s2))
            
            # Compare the pair of strings letter by 
            # letter to identify the differentiating letter
            for ptr in range(length):
                
                # If the differentiating letter is found
                if s1[ptr] != s2[ptr]:
                    
                    # Add the edge to the graph
                    adj[ord(s1[ptr]) - ord('a')].append(ord(s2[ptr]) - ord('a'))
                    break
        
        # Get the topological sort 
        # of the graph formed
        topo = self.topoSort(K, adj)
        
        # To store the answer
        ans = ""
        
        for i in range(K):
            # Add the letter to the result
            ans += chr(ord('a') + topo[i])
            ans += ' '
        
        # Return the answer
        return ans

# Example usage
N = 5
K = 4
dict = [
    "baa", "abcd", "abca", "cab", "cad"
]

sol = Solution()
ans = sol.findOrder(dict, N, K)

# Output
print("The order to characters as per alien dictionary is:", ans)
class Solution {

    /* Function to return the topological
     sorting of given graph */
    topoSort(V, adj) {
        
        // To store the In-degrees of nodes
        let inDegree = new Array(V).fill(0);
        
        // Update the in-degrees of nodes
        for (let i = 0; i < V; i++) {
            
            for (let it of adj[i]) {
                // Update the in-degree
                inDegree[it]++;
            }
        }

        // To store the result
        let ans = [];
        
        // Queue to facilitate BFS
        let q = [];
        
        // Add the nodes with no in-degree to queue
        for (let i = 0; i < V; i++) {
            if (inDegree[i] == 0) q.push(i);
        }
        
        // Until the queue is empty
        while (q.length > 0) {
            
            // Get the node
            let node = q.shift();
            
            // Add it to the answer
            ans.push(node);
            
            // Traverse the neighbours
            for (let it of 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;
    }
    
    /* Function to determine order of 
    letters based on alien dictionary */
    findOrder(dict, N, K) {
        
        // Initialise a graph of K nodes
        let adj = new Array(K).fill().map(() => []);
        
        // Compare the consecutive words
        for (let i = 0; i < N - 1; i++) {
            
            let s1 = dict[i];
            let s2 = dict[i + 1];
            let len = Math.min(s1.length, s2.length);
            
            /* Compare the pair of strings letter by 
            letter to identify the differentiating letter */
            for (let ptr = 0; ptr < len; ptr++) {
                
                // If the differentiating letter is found
                if (s1[ptr] != s2[ptr]) {
                    
                    // Add the edge to the graph
                    adj[s1.charCodeAt(ptr) - 'a'.charCodeAt(0)].push(s2.charCodeAt(ptr) - 'a'.charCodeAt(0));
                    break;
                }
            }
        }
        
        /* Get the topological sort 
        of the graph formed */
        let topo = this.topoSort(K, adj);
        
        // To store the answer
        let ans = '';
        
        for (let i = 0; i < K; i++) {
            // Add the letter to the result
            ans += String.fromCharCode('a'.charCodeAt(0) + topo[i]);
            ans += ' ';
        }
        
        // Return the answer
        return ans;
    }
}

// Example usage
const N = 5;
const K = 4;
const dict = [
    "baa", "abcd", "abca", "cab", "cad"
];

const sol = new Solution();
const ans = sol.findOrder(dict, N, K);

// Output
console.log("The order to characters as per alien dictionary is:", ans);

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.

Follow-up question for interview:

If every character matches and the largest word appears before the shortest word: For example, if “abcd” appears before “abc”, we can say the ordering is not possible.
If there exists a cyclic dependency between the characters: For example, in the dictionary: dict: {“abc”, “bat”, “ade”} there exists a cyclic dependency between 'a' and 'b' because the dictionary states 'a' < 'b' < 'a', which is not possible.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial