Hard — Graph | Topological Sort | BFS | String

The Problem

Given a list of words from an alien language sorted lexicographically, determine the order of letters in the alien alphabet. Return the alien dictionary as a string, or empty string if no valid order exists.

Approach

Build a directed graph where edges represent character ordering relationships derived from adjacent word comparisons. Use topological sorting with Kahn’s algorithm to find a valid ordering of characters, detecting cycles that indicate invalid dictionaries.

Time: O(C) · Space: O(1)

Code

from collections import defaultdict, deque

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = defaultdict(list)
        in_degree = defaultdict(int)

        for i in range(len(words) - 1):
            word1, word2 = words[i], words[i + 1]
            for j in range(min(len(word1), len(word2))):
                if word1[j] != word2[j]:
                    graph[word1[j]].append(word2[j])
                    in_degree[word2[j]] += 1
                    break

        queue = deque(char for char, indeg in in_degree.items() if indeg == 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)

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment