Alien Dictionary

86.Alien Dictionary

Graph

Topological Sort

String

Problem Statement:

Given a list of words sorted in an alien language dictionary, return the order of characters in the alien language. If no valid order exists, return an empty string.

Algorithm:

1. Use a graph-based approach with topological sorting (Kahn's algorithm).
2. Initialize two structures:
• inDegree: Tracks incoming edges for each character.
• map: Represents the adjacency list of the graph.
3. Build the graph by comparing adjacent words in the dictionary:
• Find the first differing character and add an edge between them in the graph.
• Update the inDegree for the destination character.
4. Perform topological sorting using a queue:
• Enqueue all characters with an in-degree of 0.
• Process characters, decrementing the in-degree of their neighbors, and enqueue them if their in-degree becomes 0.
5. Return the sorted order if it contains all characters; otherwise, return an empty string (no valid ordering).

Complexity:

Time: O(C), where C is the total number of characters in all words | Space: O(U + E), where U is the number of unique characters and E is the number of edges.

Java Implementation:

import java.util.*;

public class Solution {
    public String alienOrder(String[] words) {
        StringBuilder res = new StringBuilder();
        Map inDegree = new HashMap<>();
        Map> map = new HashMap<>();
        
        initialize(words, inDegree, map); // Initialize graph and in-degrees
        
        for (int i = 0; i < words.length - 1; i++) 
            getEdge(words[i], words[i + 1], inDegree, map); // Build graph edges
        
        Queue q = new LinkedList<>();
        
        // Add all characters with in-degree 0 to the queue
        for (char c : inDegree.keySet()) 
            if (inDegree.get(c) == 0) q.offer(c);
        
        // Kahn's algorithm for topological sorting
        while (!q.isEmpty()) {
            char curr = q.poll();
            res.append(curr);
            for (char c : map.get(curr)) {
                inDegree.put(c, inDegree.get(c) - 1);
                if (inDegree.get(c) == 0) q.offer(c);
            }
        }
        
        // If result length doesn't match number of unique characters, no valid ordering
        if (res.length() != map.size()) return "";
        
        return res.toString();    
    }

    // Compare two words and add an edge for the first differing character
    public void getEdge(String word1, String word2, Map inDegree, Map> map) {
        int i = 0, j = 0;
        while (i < word1.length() && j < word2.length()) {
            char c1 = word1.charAt(i++);
            char c2 = word2.charAt(j++);
            if (c1 == c2) continue;
            if (map.get(c1).contains(c2)) return; // Avoid duplicate edges
            inDegree.put(c2, inDegree.get(c2) + 1);
            map.get(c1).add(c2);
            return;
        }
    }

    // Initialize in-degree and adjacency list
    public void initialize(String[] words, Map inDegree, Map> map) {
        for (String word : words) {
            for (char c : word.toCharArray()) {
                inDegree.put(c, 0);
                map.put(c, new HashSet<>());
            }
        }
    }
}

Python Implementation:

from collections import defaultdict, deque

class Solution:
    def alienOrder(self, words):
        in_degree = defaultdict(int)
        graph = defaultdict(set)

        # Initialize in-degree and graph
        for word in words:
            for char in word:
                in_degree[char]

        # Build the graph
        for i in range(len(words) - 1):
            self.get_edge(words[i], words[i + 1], in_degree, graph)

        # Topological sort using Kahn's algorithm
        queue = deque([char for char in in_degree if in_degree[char] == 0])
        result = []

        while queue:
            char = queue.popleft()
            result.append(char)
            for neighbor in graph[char]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)

        # If all characters are not in result, return ""
        if len(result) != len(in_degree):
            return ""
        
        return ''.join(result)

    def get_edge(self, word1, word2, in_degree, graph):
        for c1, c2 in zip(word1, word2):
            if c1 != c2:
                if c2 not in graph[c1]:
                    graph[c1].add(c2)
                    in_degree[c2] += 1
                return

C++ Implementation:

#include 
#include 
#include 
#include 
#include 
using namespace std;

class Solution {
public:
    string alienOrder(vector& words) {
        unordered_map in_degree;
        unordered_map> graph;

        // Initialize in-degree and graph
        for (const string& word : words) {
            for (char c : word) {
                in_degree[c];
            }
        }

        // Build the graph
        for (int i = 0; i < words.size() - 1; ++i) {
            getEdge(words[i], words[i + 1], in_degree, graph);
        }

        // Topological sort using Kahn's algorithm
        queue q;
        for (const auto& [c, degree] : in_degree) {
            if (degree == 0) q.push(c);
        }

        string result;
        while (!q.empty()) {
            char c = q.front();
            q.pop();
            result += c;
            for (char neighbor : graph[c]) {
                if (--in_degree[neighbor] == 0) q.push(neighbor);
            }
        }

        // If all characters are not in result, return ""
        if (result.size() != in_degree.size()) return "";
        
        return result;
    }

private:
    void getEdge(const string& word1, const string& word2, unordered_map& in_degree, unordered_map>& graph) {
        for (int i = 0; i < min(word1.size(), word2.size()); ++i) {
            char c1 = word1[i], c2 = word2[i];
            if (c1 != c2) {
                if (!graph[c1].count(c2)) {
                    graph[c1].insert(c2);
                    ++in_degree[c2];
                }
                return;
            }
        }
    }
};