leetcode-269 Alien Dictionary

# Given a sorted dictionary of an alien language, derive the order of characters.

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        from collections import defaultdict, deque

        # Build graph
        graph = defaultdict(set)
        in_degree = {c: 0 for word in words for c in word}

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

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

            # Find first different character
            for j in range(min_len):
                if word1[j] != word2[j]:
                    if word2[j] not in graph[word1[j]]:
                        graph[word1[j]].add(word2[j])
                        in_degree[word2[j]] += 1
                    break

        # Topological sort
        queue = deque([c for c in in_degree if in_degree[c] == 0])
        result = []

        while queue:
            c = queue.popleft()
            result.append(c)

            for neighbor in graph[c]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)

        return ''.join(result) if len(result) == len(in_degree) else ""

# Time: O(C) where C is total characters, Space: O(1) - at most 26 chars
# AirBnB: Tests topological sort and edge case handling