LeetCode 269: Alien Dictionary Solution in Python – A Step-by-Step Guide

What Is LeetCode 269: Alien Dictionary?

In LeetCode 269: Alien Dictionary, you’re given a list of strings words sorted in an alien language’s lexicographical order, and your task is to return a string representing the order of characters in that alien alphabet. If no valid order exists (e.g., due to contradictions), return an empty string. For example, if "wrt" comes before "wrf," then 't' must come before 'f' in the alien alphabet. This problem introduces graph-based ordering, related to challenges like LeetCode 207: Course Schedule, but focuses on deriving a character sequence from word comparisons.

Problem Statement

• Input: A list of strings words sorted lexicographically in an alien alphabet.
• Output: A string—the order of characters in the alien alphabet, or "" if invalid.
• Rules: Words imply character order (e.g., "ab" before "ac" → 'b' < 'c'); no valid order if cyclic or contradictory.

Constraints

• words.length: 1 to 100.
• words[i].length: 1 to 20.
• Characters: Lowercase English letters (a-z).
• Words are sorted in alien order.

Examples

• Input: words = ["wrt", "wrf", "er", "ett", "rftt"]
• Output: "wertf" (w < e < r < t < f).
• Input: words = ["z", "x"]
• Output: "zx" (z < x).
• Input: words = ["z", "x", "z"]
• Output: "" (contradiction: z < x and x < z).

Understanding the Problem: Decoding the Alien Alphabet

To solve LeetCode 269: Alien Dictionary in Python, we need to deduce the order of characters based on how words are sorted. If "wrt" comes before "wrf," the first differing character pair (t vs. f) tells us t < f. We build a graph where edges show these relationships (e.g., t → f), then order the characters so each comes before its neighbors. A simple way—guessing orders and checking—won’t work efficiently. We’ll use two methods: 1. Best Solution (Topological Sort with Graph): O(N + C) time—fast and precise (N is total characters, C is unique chars). 2. Alternative Solution (DFS with Cycle Detection): O(N + C)—clear but more complex.

Let’s dive into the best solution with a friendly, detailed walkthrough.

Best Solution: Topological Sort with Graph Building

Why This Is the Best Solution

The topological sort with graph building approach is the top pick for LeetCode 269 because it runs in O(N + C) time—super efficient—and uses a straightforward process to build a graph of character relationships, then sorts them into a valid order. It’s like piecing together a puzzle where each clue (word pair) locks in part of the picture, making it both fast and easy to grasp once you see it in action.

How It Works

Picture this solution as mapping out a family tree: you compare words to find who comes before whom, draw arrows between characters (like a family hierarchy), and then line them up so every parent precedes their kids. If there’s a loop or mismatch, it’s invalid. Here’s how it works, step-by-step, explained simply:

• Step 1: Build the Graph:
• Compare adjacent word pairs to find differing characters.
• For "wrt" and "wrf": same 'w', 'r', differ at 't' vs 'f' → t < f, add edge t → f.
• Use a dictionary for edges (adjacency list) and track in-degrees (how many arrows point to each char).
• Step 2: Check for Validity:
• If a word is a prefix of the next but shorter (e.g., "ab" after "abc"), it’s invalid—return "".
• Step 3: Topological Sort with Queue:
• Start with characters having no incoming edges (in-degree 0)—they come first.
• Use a queue: pop a char, add it to the result, reduce in-degrees of its neighbors, add any new 0 in-degree chars.
• Step 4: Validate the Result:
• If the result length equals unique characters, it’s valid; otherwise, there’s a cycle—return "".

It’s like untangling a web—start with free ends and work your way through!

Step-by-Step Example

Example: words = ["wrt", "wrf", "er", "ett", "rftt"]

• Step 1: Build graph:
• "wrt" vs "wrf": t → f.
• "wrf" vs "er": w → e.
• "er" vs "ett": r → t.
• "ett" vs "rftt": e → r.
• Graph: {t: [f], w: [e], r: [t], e: [r]}, In-degree: {f:1, e:1, t:1, r:1, w:0}.
• Step 2: No prefix issues.
• Step 3: Topological sort:
• Queue: [w], Result = "w".
• Pop w: e’s in-degree → 0, Queue: [e], Result = "we".
• Pop e: r’s in-degree → 0, Queue: [r], Result = "wer".
• Pop r: t’s in-degree → 0, Queue: [t], Result = "wert".
• Pop t: f’s in-degree → 0, Queue: [f], Result = "wertf".
• Pop f: Queue empty, Result = "wertf".
• Step 4: 5 chars, matches unique count (w, e, r, t, f).
• Result: "wertf".

Example: words = ["z", "x", "z"]

• Step 1: "z" vs "x": z → x, "x" vs "z": x → z (cycle).
• Step 3: Topological sort fails (cycle detected).
• Result: "".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained in a friendly way:

Copy codefrom collections import defaultdict, deque

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        # Step 1: Build graph and in-degree
        graph = defaultdict(list)
        in_degree = defaultdict(int)
        chars = set("".join(words))  # All unique characters

        # Compare adjacent words
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            # Check prefix invalidity
            if len(w1) > len(w2) and w1.startswith(w2):
                return ""
            # Find first differing char
            for j in range(len(w1)):
                if j >= len(w2):
                    break
                if w1[j] != w2[j]:
                    graph[w1[j]].append(w2[j])
                    in_degree[w2[j]] += 1
                    break

        # Step 2: Topological sort with queue
        queue = deque([c for c in chars if in_degree[c] == 0])
        result = []

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

        # Step 3: Check validity
        return "".join(result) if len(result) == len(chars) else ""

• Line 4-7: Set up graph (char → list of next chars) and in-degree (char → count of incoming edges); get all unique chars.
• Line 9-20: Build graph:
• Compare word pairs, check prefix rule.
• First differing char: add edge, increase in-degree.
• Line 22-30: Topological sort:
• Start queue with 0 in-degree chars.
• Pop, add to result, update neighbors’ in-degrees, add new 0s.
• Line 32: If result length matches unique chars, return order; else "" (cycle).

• Time Complexity: O(N + C)—N is total chars in words, C is unique chars.
• Space Complexity: O(C)—graph and queue.

This solution is like a word detective—map the clues and line them up!

Alternative Solution: DFS with Cycle Detection

Why an Alternative Approach?

The DFS approach explores the graph like a maze, checking for cycles and building the order as it backtracks. It’s also O(N + C) but uses recursion, offering a different lens on the problem—more like following paths than queuing up.

How It Works

Think of this as tracing family lines: start at a character, follow its descendants, and list them in reverse order after exploring, but stop if you loop back. Here’s how it works, step-by-step:

• Step 1: Build the same graph as above.
• Step 2: DFS with three states (unvisited, visiting, visited) to detect cycles.
• Step 3: Build order by adding chars after their children are processed.

Step-by-Step Example

Example: words = ["wrt", "wrf", "er", "ett", "rftt"]

• Graph: {t: [f], w: [e], r: [t], e: [r]}.
• DFS:
• Start w: Explore e → r → t → f.
• Order (post-order): f, t, r, e, w → "wertf".
• Result: "wertf".

Code for DFS Approach

Copy codefrom collections import defaultdict

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        # Build graph
        graph = defaultdict(list)
        chars = set("".join(words))
        for i in range(len(words) - 1):
            w1, w2 = words[i], words[i + 1]
            if len(w1) > len(w2) and w1.startswith(w2):
                return ""
            for j in range(len(w1)):
                if j >= len(w2):
                    break
                if w1[j] != w2[j]:
                    graph[w1[j]].append(w2[j])
                    break

        # DFS with cycle detection
        visited = {}  # 0: unvisited, 1: visiting, 2: visited
        result = []

        def dfs(char):
            if char in visited:
                return visited[char] == 2  # False if visiting (cycle)
            visited[char] = 1  # Mark as visiting
            for neighbor in graph[char]:
                if not dfs(neighbor):
                    return False
            visited[char] = 2  # Mark as visited
            result.append(char)
            return True

        # Run DFS on all chars
        for char in chars:
            if char not in visited:
                if not dfs(char):
                    return ""

        return "".join(result[::-1])  # Reverse for correct order

• Time Complexity: O(N + C)—graph build and DFS.
• Space Complexity: O(C)—graph and recursion.

It’s a deep dive but works well.

Comparing the Two Solutions

• Best Solution (Topological Sort):
• Pros: O(N + C) time, O(C) space, intuitive queue.
• Cons: Queue logic to learn.
• Alternative Solution (DFS):
• Pros: O(N + C) time, O(C) space, path-based.
• Cons: Recursion and cycle check more complex.

Topological sort wins for clarity.

Additional Examples and Edge Cases

Simple Pair

• ["z", "x"] → "zx"

Invalid

• ["z", "z"] → "z"

Complex

• ["ab", "adc"] → "abc"

Both handle these well.

Complexity Breakdown

• Topological Sort:
• Time: O(N + C)—linear.
• Space: O(C)—graph.
• DFS:
• Time: O(N + C)—linear.
• Space: O(C)—graph and stack.

Both are efficient, sort is simpler.

Key Takeaways

• Topological Sort: Queue builds order.
• DFS: Paths detect cycles.
• Graphs: Map relationships.
• Python Tip: Dicts make graphs easy—see [Python Basics](/python/basics).

Final Thoughts: Decode Like a Pro

LeetCode 269: Alien Dictionary in Python is a thrilling graph puzzle. The topological sort solution maps and orders efficiently, while DFS traces paths. Want more? Try LeetCode 207: Course Schedule or LeetCode 210: Course Schedule II. Ready to decode? Head to Solve LeetCode 269 on LeetCode and crack that alien alphabet today!