🟥 Alien Dictionary (#269) 🔒

🔗 Problem Link

• LeetCode - Alien Dictionary (Premium)
• NeetCode - Alien Dictionary

📋 Problem Statement

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.

Note: This is a premium LeetCode problem, but available for free on NeetCode.

💡 Examples

Example 1

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

Example 2

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

Example 3

Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return "".

🔑 Key Insights & Approach

Core Observation: Build directed graph from character ordering, then perform topological sort. Detect cycles for invalid input.

Why Topological Sort?

• O(C) time where C = total chars in all words
• Build graph by comparing adjacent words
• Detect cycles = invalid ordering
• DFS or Kahn's algorithm

Approaches:

1. DFS topological sort: O(C) time, O(1) space for alphabet
2. BFS (Kahn's algorithm): O(C) time, O(1) space

Pattern: "Topological Sort" for ordering dependencies.

🐍 Solution: Python

Approach: DFS Topological Sort

Time Complexity: O(C) | Space Complexity: O(1)

from typing import List
from collections import defaultdict

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        # Build adjacency list
        graph = {c: set() for word in words for c in word}

        # Add edges from adjacent word comparisons
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            min_len = min(len(w1), len(w2))

            # Check for invalid case: w1 is prefix of w2 but longer
            if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
                return ""

            # Find first difference
            for j in range(min_len):
                if w1[j] != w2[j]:
                    graph[w1[j]].add(w2[j])
                    break

        # Topological sort using DFS
        visited = {}  # False = visiting, True = visited
        result = []

        def dfs(char):
            if char in visited:
                return visited[char]

            visited[char] = False  # Mark as visiting

            for neighbor in graph[char]:
                if not dfs(neighbor):
                    return False

            visited[char] = True  # Mark as visited
            result.append(char)
            return True

        for char in graph:
            if not dfs(char):
                return ""

        return "".join(reversed(result))

Approach 2: BFS (Kahn's Algorithm)

Time Complexity: O(C) | Space Complexity: O(1)

from typing import List
from collections import defaultdict, deque

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = {c: set() for word in words for c in word}
        in_degree = {c: 0 for word in words for c in word}

        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            min_len = min(len(w1), len(w2))

            if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
                return ""

            for j in range(min_len):
                if w1[j] != w2[j]:
                    if w2[j] not in graph[w1[j]]:
                        graph[w1[j]].add(w2[j])
                        in_degree[w2[j]] += 1
                    break

        # BFS with Kahn's algorithm
        queue = deque([c for c in in_degree if in_degree[c] == 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 len(result) < len(in_degree):
            return ""

        return "".join(result)

🔵 Solution: Golang

Approach: DFS

Time Complexity: O(C) | Space Complexity: O(1)

func alienOrder(words []string) string {
    graph := make(map[byte]map[byte]bool)

    // Initialize graph
    for _, word := range words {
        for i := 0; i < len(word); i++ {
            if graph[word[i]] == nil {
                graph[word[i]] = make(map[byte]bool)
            }
        }
    }

    // Build edges
    for i := 0; i < len(words)-1; i++ {
        w1, w2 := words[i], words[i+1]
        minLen := len(w1)
        if len(w2) < minLen {
            minLen = len(w2)
        }

        if len(w1) > len(w2) && w1[:minLen] == w2[:minLen] {
            return ""
        }

        for j := 0; j < minLen; j++ {
            if w1[j] != w2[j] {
                graph[w1[j]][w2[j]] = true
                break
            }
        }
    }

    visited := make(map[byte]int) // 0: unvisited, 1: visiting, 2: visited
    result := []byte{}

    var dfs func(char byte) bool
    dfs = func(char byte) bool {
        if visited[char] == 1 {
            return false
        }
        if visited[char] == 2 {
            return true
        }

        visited[char] = 1
        for neighbor := range graph[char] {
            if !dfs(neighbor) {
                return false
            }
        }

        visited[char] = 2
        result = append(result, char)
        return true
    }

    for char := range graph {
        if !dfs(char) {
            return ""
        }
    }

    // Reverse result
    for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
        result[i], result[j] = result[j], result[i]
    }

    return string(result)
}

📚 References

• NeetCode - Alien Dictionary