Start learning free

LESSON 476 OF 536 · GRAPHS

Alien Dictionary in Python: Topological Sort on Letters

Practice O(C) Read the full explanation

An alien language uses the lowercase English letters, but in an order you don't know. You are given a list of strings words from the dictionary of this language: the words are sorted in the alien alphabetical order.

Two words are compared letter by letter, as in any dictionary: at the first position where they differ, the word with the earlier letter comes first. If no position differs because one word is the beginning (a prefix) of the other, the shorter word comes first, so "ab" always comes before "abc".

Return a string with every letter that appears in words, each once, in the order of the alien alphabet. If the words contradict themselves, so that no order of the letters makes them sorted, return "" (an empty string). If several orders work, return the one that comes first in the usual alphabetical order: that makes the answer unique.

 

Example 1:

Input: words = ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"
Explanation: Each pair of neighbouring words tells us one thing, from the first letters where they differ:
    "wrt" before "wrf":  t comes before f
    "wrf" before "er":   w comes before e
    "er" before "ett":   r comes before t
    "ett" before "rftt": e comes before r
Chained together: w → e → r → t → f. These are all the letters of the words, and this is the only order that works.

Example 2:

Input: words = ["z", "x", "z"]
Output: ""
Explanation: "z" before "x" says z comes before x, but "x" before "z" says x comes before z.
The two facts form a cycle, so no order of the letters can make this list sorted.

Example 3:

Input: words = ["cb", "ca"]
Output: "bac"
Explanation: The words differ first at their second letters, so b comes before a. Nothing tells us where c goes.
The orders "bac", "bca" and "cba" all work; "bac" comes first alphabetically.

 

Constraints:

  • 1 <= words.length <= 104
  • 1 <= words[i].length <= 20
  • words[i] consists of lowercase English letters. The same word can appear more than once.

Note:

Turn the facts into arrows between letters: an order that agrees with every arrow is a topological order, which Kahn's algorithm from Course Schedule finds; taking the alphabetically smallest ready letter each time gives the answer above. Neighbouring words are enough, so the time is O(C), where C is the total number of letters in words; comparing every pair of words would take O(n2) comparisons for n words.

STEP 1 OF 29
    Ctrl + Enter to check

    PYTHON · GRAPHS

    Alien Dictionary in Python, explained

    Problem overview

    An alien language uses the lowercase English letters in an unknown order. The method alienOrder receives a list words that is sorted in that alien order, and returns a string holding every letter that appears in words, once each, in the alien alphabet's order.

    Words are compared as in any dictionary: at the first position where two words differ, the one with the earlier letter comes first. If one word is a prefix of the other, the shorter one comes first, so "ab" always comes before "abc". If the words contradict themselves, so that no order of letters can make them sorted, the method returns "". When several orders work, it returns the one that comes first in the usual alphabetical order, which makes the answer unique.

    Take ["wrt", "wrf", "er", "ett", "rftt"]. Each pair of neighbouring words gives one fact, from the first letters where they differ:

    wrt  before wrf:   t before f
wrf  before er:    w before e
er   before ett:   r before t
ett  before rftt:  e before r

    Chained together, w → e → r → t → f, so the answer is "wertf". For ["z", "x", "z"] the facts "z before x" and "x before z" contradict each other, so the answer is "". For ["cb", "ca"] the only fact is "b before a". The letter c is unconstrained, and of the working orders "bac", "bca" and "cba", the first alphabetically is "bac".

    Approach: turn the facts into arrows

    Each fact is an arrow from one letter to another. An order that agrees with every arrow is a topological order of this graph of letters. It exists only if the graph has no cycle, and Kahn's algorithm finds it: keep, for every letter, the number of arrows pointing at it that aren't placed yet (its in-degree), repeatedly place a letter whose count is 0, and lower the counts of the letters it points to. Taking the alphabetically smallest ready letter each round gives the unique answer the statement asks for. If at some point letters are still waiting but none is ready, they wait for each other in a cycle, and the answer is "".

    Comparing neighbouring words is enough. If every word is in order with the next one, the whole list is sorted, so other pairs add no new facts. This keeps the work proportional to the total number of letters. Comparing every pair would take a quadratic number of comparisons in the number of words.

    Two special cases come from the prefix rule. If the words differ at some position, they give one arrow, and the letters after that position say nothing. If one word runs out first and it is the second of the pair, such as "abc" followed by "ab", no alphabet can sort them, so the answer is "". If the first one is the shorter, or the two are equal, there is no fact at all.

    Step by step

    1. Create waiting as 26 False values, one per letter. waiting[k] will be True while letter k appears in the words but isn't in the answer yet. With only 26 letters, a list indexed by letter is simpler than a dict.
    2. Start letters at 0. It counts the distinct letters, so the answer is complete when its length reaches this number.
    3. Loop over each word and, inside it, over each character c.
    4. Test not waiting[ord(c) - ord('a')]. ord gives a character's code, and a to z have consecutive codes, so the expression is 0 for a up to 25 for z.
    5. Mark the letter as True and add 1 to letters. The if ensures each letter is counted once, at its first appearance.
    6. Build graph as 26 empty lists with a list comprehension. graph[a] holds the letters that must come after letter a.
    7. Create inDegree as 26 zeros. inDegree[b] counts the unplaced letters that must come before b.
    8. Loop i over range(len(words) - 1). The pair is first = words[i] and second = words[i + 1].
    9. Find the first difference. Start j at 0 and, in a while loop, add 1 while j is inside both words and first[j] == second[j]. The checks run left to right, so the characters are read only while j is valid.
    10. If j is still inside both words, the letters at j are the first that differ. Append the index of second[j] to graph at the index of first[j], and add 1 to inDegree at the index of second[j]. Two pairs can give the same arrow. Each copy is counted here and removed once later, so that is fine.
    11. elif len(first) > len(second): the second word is a prefix of the first, which no alphabet allows. Return "".
    12. Start order as an empty string.
    13. Loop while len(order) < letters. Each round places one letter.
    14. Scan for the smallest ready letter. Start letter at 0 and add 1 while letter < 26 and the letter isn't waiting or still has arrows coming in. The first letter the scan stops at is the smallest ready one.
    15. If letter == 26, nothing is ready: return "".
    16. Place the letter. Set waiting[letter] to False and append chr(ord('a') + letter) to order. chr is the opposite of ord.
    17. Release the letters after it. For each nextLetter in graph[letter], subtract 1 from inDegree[nextLetter].
    18. Return order after the loop.

    The solution in Python

    class Solution:
    def alienOrder(self, words: List[str]) -> str:
        waiting = [False] * 26
        letters = 0
        for word in words:
            for c in word:
                if not waiting[ord(c) - ord('a')]:
                    waiting[ord(c) - ord('a')] = True
                    letters += 1
        graph = [[] for _ in range(26)]
        inDegree = [0] * 26
        for i in range(len(words) - 1):
            first = words[i]
            second = words[i + 1]
            j = 0
            while j < len(first) and j < len(second) and first[j] == second[j]:
                j += 1
            if j < len(first) and j < len(second):
                graph[ord(first[j]) - ord('a')].append(ord(second[j]) - ord('a'))
                inDegree[ord(second[j]) - ord('a')] += 1
            elif len(first) > len(second):
                return ""
        order = ""
        while len(order) < letters:
            letter = 0
            while letter < 26 and (not waiting[letter] or inDegree[letter] > 0):
                letter += 1
            if letter == 26:
                return ""
            waiting[letter] = False
            order += chr(ord('a') + letter)
            for nextLetter in graph[letter]:
                inDegree[nextLetter] -= 1
        return order

    Python details worth a closer look:

    • A list comprehension for graph. [[] for _ in range(26)] creates 26 separate lists. [[]] * 26 repeats one list object 26 times: after g = [[]] * 3 and g[0].append(1), g is [[1], [1], [1]]. With the comprehension, the same two lines leave [[1], [], []].
    • ord and chr. ord('c') - ord('a') is 2, and chr(ord('a') + 2) is 'c'. They convert between a letter and its index in the lists.
    • Short-circuit and. In j < len(first) and j < len(second) and first[j] == second[j], the comparison is evaluated only when j is a valid index in both words, so there is no IndexError.
    • Building a string with +=. Strings are immutable, so each order += ... creates a new string. With at most 26 letters that cost doesn't matter.
    • The parenthesised condition. letter < 26 comes first so that waiting[letter] is never read at index 26.

    Complexity

    Time: O(C), where C is the total number of letters in words. Collecting the letters reads each character once. Comparing neighbouring words takes at most the length of the shorter word per pair, so also O(C). The ordering loop places at most 26 letters, and each round scans at most 26 positions, which is a constant.

    Space: O(1) beyond the input. The lists have 26 entries each, and the arrows are at most one per pair of neighbouring words.

    Edge cases and common mistakes

    • A prefix in the wrong order. ["abc", "ab"] returns "", because the longer word can't come first. ["ab", "abc"] is fine and returns "abc".
    • Cycles. ["z", "x", "z"] returns "".
    • A single word or equal words. ["a"] returns "a" and ["z", "z"] returns "z", because no facts are produced and every letter is free.
    • Letters without any arrow. They still belong in the answer. The count letters makes sure they are placed, and the scan picks them in alphabetical order.
    • Not taking the smallest ready letter. Any ready letter gives a valid order, but only the smallest each round gives the alphabetically first one. For ["za", "zb", "ca", "cb"] the answer is "abzc".
    • Comparing only the first letters. Words can share a long prefix. The fact comes from the first position where they differ.
    • Using more than the first difference. Letters after the first differing position say nothing about the order.

    Testing

    • words = ["wrt", "wrf", "er", "ett", "rftt"] gives "wertf".
    • words = ["z", "x", "z"] gives "".
    • words = ["cb", "ca"] gives "bac".
    • words = ["abc", "ab"] gives "".
    • words = ["ab", "abc"] gives "abc".
    • words = ["a"] gives "a".
    • words = ["ba", "bc", "ac", "cab"] gives "bac".
    • words = ["za", "zb", "ca", "cb"] gives "abzc".
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free