LeetEye LeetEye
Hard Advanced Graphs ~5 min

Alien Dictionary

advanced-graphs alien-dictionary

Problem

There is a new alien language that uses the English alphabet. However, the order of 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.

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: "" (invalid - z can't come before and after x)
Key Insight

Compare adjacent words to extract "char A comes before char B" relationships. Then topological sort.

Compare adjacent words to extract 'char A before char B' edges. Build graph. Topological sort. Cycle = invalid.

How to Approach This Problem

Pattern Recognition: When you see keywords like alien dictionary advanced-graphs, think Advanced Graphs.

Step-by-Step Reasoning

1 From sorted words ["abc", "abd"]:
Answer: c < d (only)
First difference is at position 2: 'c' vs 'd'. So c comes before d.
2 For words ["ab", "a"]:
Answer: This is invalid ordering
A prefix ("a") should come BEFORE a longer word ("ab"). This violates that.
3 From n sorted words, we get:
Answer: At most n-1 constraints
We compare adjacent pairs. n words = n-1 pairs = at most n-1 constraints.
4 We have edges like (a→b means a before b). Next:
Answer: Topological sort
Constraints form a directed graph. Topological sort gives valid ordering.
5 No valid ordering exists when:
Answer: Graph has a cycle
Cycle means a < b < ... < a, which is impossible.

Solution

from collections import defaultdict, deque

def alienOrder(words: List[str]) -> str:
    # Build graph
    graph = defaultdict(set)
    in_degree = {c: 0 for word in words for c in word}
    
    # Compare adjacent words
    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: prefix comes after longer word
        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]:
                if w2[j] not in graph[w1[j]]:
                    graph[w1[j]].add(w2[j])
                    in_degree[w2[j]] += 1
                break
    
    # Topological sort (Kahn's algorithm)
    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)
    
    # Check for cycle
    if len(result) != len(in_degree):
        return ""
    
    return "".join(result)

Complexity Analysis

Time O(C)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Advanced Graphs problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye