Alien Dictionary hard

Problem Statement

There is a hidden word in the given alien dictionary. You are given a list of words from an alien language, and you need to find the order of letters in the alien alphabet. Each word in the list is a sequence of letters from the alien alphabet. The order of words in the list gives you clues about the relative order of letters. Specifically, if word word1 comes before word2 in the list, and there is an index i where word1[i] != word2[i], then word1[i] must come before word2[i] in the alien alphabet. If there is no such ordering, return the empty string "".

Example 1

Input: words = ["wrt","wrf","er","ett","rftt"] Output: "wertf"

Example 2

Input: words = ["z","x"] Output: "zx"

Steps

1. Build the Graph: Create a directed graph where each node represents a letter from the alien alphabet. An edge from letter a to letter b indicates that a comes before b in the alien alphabet. We traverse the list of words, comparing consecutive words to find these ordering relationships.

2. Detect Cycles: Check for cycles in the directed graph. If a cycle exists, it means there is a contradiction in the given word order (e.g., a < b and b < a), and no valid ordering exists. We can use topological sort to detect cycles.

3. Topological Sort: If no cycles are found, perform a topological sort on the graph. Topological sort arranges the nodes such that for every directed edge from node a to node b, node a appears before node b in the sorted order. The result of the topological sort will be the valid alien alphabet order.

Explanation

The algorithm works by constructing a directed graph representing the relationships between letters based on the order of words. If a cycle is detected, it signifies an inconsistency in the word order, hence no valid alien alphabet is possible. Otherwise, topological sort provides the lexicographical ordering of the letters. This approach efficiently handles the constraints and provides the correct order if one exists.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public string AlienOrder(string[] words) {
        Dictionary<char, HashSet<char>> graph = new Dictionary<char, HashSet<char>>();
        HashSet<char> nodes = new HashSet<char>();

        // Build the graph
        for (int i = 0; i < words.Length; i++) {
            foreach (char c in words[i]) {
                nodes.Add(c);
            }
            if (i > 0) {
                string word1 = words[i - 1];
                string word2 = words[i];
                int minLen = Math.Min(word1.Length, word2.Length);
                for (int j = 0; j < minLen; j++) {
                    if (word1[j] != word2[j]) {
                        if (!graph.ContainsKey(word1[j])) {
                            graph[word1[j]] = new HashSet<char>();
                        }
                        if (!graph[word1[j]].Contains(word2[j])) {
                            graph[word1[j]].Add(word2[j]);
                        }
                        break;
                    }
                    if (j == minLen - 1 && word1.Length > word2.Length) return ""; //Invalid Input
                }
            }
        }

        //Topological Sort using Kahn's Algorithm
        Dictionary<char, int> inDegree = new Dictionary<char>();
        foreach (char c in nodes) inDegree[c] = 0;
        foreach (var entry in graph) {
            foreach (char neighbor in entry.Value) {
                inDegree[neighbor]++;
            }
        }

        Queue<char> queue = new Queue<char>();
        foreach (var entry in inDegree) {
            if (entry.Value == 0) queue.Enqueue(entry.Key);
        }

        StringBuilder sb = new StringBuilder();
        while (queue.Count > 0) {
            char curr = queue.Dequeue();
            sb.Append(curr);
            if (graph.ContainsKey(curr)) {
                foreach (char neighbor in graph[curr]) {
                    inDegree[neighbor]--;
                    if (inDegree[neighbor] == 0) queue.Enqueue(neighbor);
                }
            }
        }

        return sb.Length == nodes.Count ? sb.ToString() : "";

    }
}

Complexity

• Time Complexity: O(V + E), where V is the number of unique letters (vertices) and E is the number of ordering constraints (edges) in the graph. Building the graph, checking in-degrees, and topological sort all take linear time.

• Space Complexity: O(V + E), primarily due to the adjacency list representation of the graph and the queue used in topological sort. The inDegree dictionary also contributes to this space complexity.