HardArrayStringDepth-First SearchBreadth-First SearchGraphTopological Sort

Alien Dictionary

1 approach, code in every language

You are given a list of words written in an alien language. Within this language the letters are drawn from the usual lowercase English alphabet, but their relative order is unknown.

The words are provided in an order that is lexicographically sorted according to the rules of this alien language. Using only that ordering information, determine a possible sequence of the distinct letters that appear, from smallest to largest.

Return any valid ordering as a string. If no consistent ordering exists, return an empty string. If several orderings are valid, returning any one of them is acceptable.

Example 1

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

Output: "wertf"

Comparing neighbors yields t before f, w before e, r before t, and e before r, which chains into the order w, e, r, t, f.

Example 2

Input: words = ["abc","ab"]

Output: ""

A longer word appears before one of its own prefixes, which can never happen in a valid sorted list, so no ordering exists.

Constraints

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of only lowercase English letters.

Build Ordering Graph + Kahn's Topological Sort

Derive precedence edges from adjacent words, then topologically sort the letters with Kahn's algorithm.

Loading animation…

Intuition

The sorted order between two neighboring words is decided by the first position where their characters differ: the earlier word's character must come before the later word's character in the alien alphabet. Each such comparison contributes exactly one directed edge between two letters. Collecting these edges builds a precedence graph over every letter that appears in the input. A topological order of that graph is precisely a valid alphabet, and Kahn's algorithm produces one while simultaneously exposing contradictions. If a letter never becomes free of its dependencies, the constraints contain a cycle and no ordering can exist. We also guard the special invalid case where a longer word precedes one of its own prefixes.

Algorithm walkthrough

1Register every distinct letter across all words with an in-degree of zero so that isolated letters still appear in the result.
2For each adjacent pair of words, scan until the first differing character, then add an edge from the earlier word's letter to the later word's letter and increment the target's in-degree.
3If the words share a common prefix but the earlier word is longer (for example "abc" before "ab"), the input is invalid, so return an empty string immediately.
4Seed a queue with every letter whose in-degree is zero, then repeatedly pop a letter, append it to the answer, and decrement its neighbors, enqueuing any that reach in-degree zero.
5If the produced string contains every seen letter, return it; otherwise a cycle prevented a full ordering, so return an empty string.

Implementation

from collections import deque, defaultdict
from typing import List

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

        for i in range(len(words) - 1):
            first, second = words[i], words[i + 1]
            min_len = min(len(first), len(second))
            if len(first) > len(second) and first[:min_len] == second[:min_len]:
                return ""
            for j in range(min_len):
                if first[j] != second[j]:
                    if second[j] not in adj[first[j]]:
                        adj[first[j]].add(second[j])
                        indegree[second[j]] += 1
                    break

        queue = deque([c for c in indegree if indegree[c] == 0])
        result = []
        while queue:
            c = queue.popleft()
            result.append(c)
            for nxt in adj[c]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        if len(result) < len(indegree):
            return ""
        return "".join(result)

Time

O(C), where C is the total number of characters across all words

Space

O(1), since the graph holds at most 26 letters and their edges

Only lowercase English letters appear, so the alphabet and edge set are bounded by constants.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Lost Collation Order is our own problem on the technique behind Alien Dictionary: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free