Start learning free

LESSON 480 OF 540 · GRAPHS

Alien Dictionary in Go: Topological Sort in O(C)

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 an array 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

    GO · GRAPHS

    Alien Dictionary in Go, explained

    Problem overview

    An alien language uses the lowercase English letters in an unknown order. The function alienOrder gets words, a slice of words sorted in that alien alphabet, and returns a string holding every letter that appears in the words, once each, in the alien order. If the words contradict themselves, so that no order of the letters could make them sorted, it returns "". If several orders work, it returns the one that comes first in the usual alphabetical order, which makes the answer unique.

    Words are compared as in any dictionary: at the first position where they differ, the word with the earlier letter comes first. If one word is a prefix of the other, the shorter one comes first, so "ab" always precedes "abc".

    For ["wrt", "wrf", "er", "ett", "rftt"] the answer is "wertf". Each pair of neighbouring words gives one fact: t before f, w before e, r before t, and e before r. Chained, that is w, e, r, t, f. For ["z", "x", "z"] the answer is "", because the pairs say both "z before x" and "x before z". For ["cb", "ca"] only "b before a" is known, so "bac", "bca" and "cba" all work, and "bac" is the alphabetically first.

    The cost is O(C), where C is the total number of letters in words.

    Approach: facts as arrows, then Kahn's algorithm

    Turn each fact into an arrow between two letters. An order that agrees with every arrow is a topological order of the resulting graph, and Kahn's algorithm finds one: repeatedly place a letter that has no unplaced letter before it. Taking the alphabetically smallest such letter each time gives the unique answer the problem asks for.

    Neighbouring words are enough. If every word is in order with the next one, the whole list is sorted, so other pairs add no new facts. Comparing every pair of words would cost O(n²) comparisons for n words.

    Each neighbouring pair gives at most one arrow, from the first position where the words differ. The letters after that position say nothing. If no position differs because one word runs out, there is no arrow, unless the first word is the longer one: then the second is a prefix of the first and should have come first in any alphabet, so the list contradicts itself.

    Step by step

    1. Mark the letters that appear. Create waiting, a slice of 26 bools. waiting[k] is true while letter number k appears in the words but isn't in the answer yet. With only 26 possible letters, a slice indexed by letter is simpler than a map.
    2. Count the different letters in letters, starting at 0. The answer is complete when its length reaches this number.
    3. Loop over each word, then over each character c of the word.
    4. Test !waiting[c - 'a']. The letters a to z are consecutive, so c - 'a' is 0 for a, 1 for b, up to 25 for z.
    5. Mark the letter and count it. Set waiting[c - 'a'] = true and add 1 to letters. The if makes sure each letter is counted once.
    6. Build the graph: graph := make([][]int, 26). graph[a] holds the letters that must come after letter a. The 26 inner slices start as nil, and append works on a nil slice.
    7. Create inDegree, a slice of 26 ints. inDegree[b] counts the arrows pointing into b from letters not placed yet. A letter can be placed as soon as its count is 0.
    8. Loop over neighbouring pairs: i from 0 while i < len(words) - 1. Store words[i] as first and words[i + 1] as second.
    9. Find the first difference. Start j at 0 and advance it while it is inside both words and first[j] == second[j]. The checks run left to right, so the letters are read only while j is inside both.
    10. If j is still inside both words, the letters at j are the first that differ. Since first comes before second, first[j] comes before second[j] in the alien alphabet.
    11. Add the arrow: append int(second[j] - 'a') to graph[first[j] - 'a'], storing the result back, and add 1 to inDegree[second[j] - 'a']. Two pairs may give the same arrow. Each copy is counted here and removed once later, so that is fine.
    12. Otherwise, with } else if len(first) > len(second), return "": the shorter word is a prefix of the longer one but comes after it.
    13. Start Kahn's algorithm. Create order, an empty string, and loop while len(order) < letters. Each round places one letter.
    14. Find the smallest ready letter. Start letter at 0 and advance it while letter < 26 and the letter is not waiting or still has arrows coming in (!waiting[letter] || inDegree[letter] > 0). A ready letter appears in the words, isn't placed, and has every earlier letter placed. Scanning from a to z finds the smallest one.
    15. If letter == 26, return "". Letters are still waiting, but each waits for another waiting letter: they form a cycle.
    16. Place the letter. Set waiting[letter] = false, add string(rune('a' + letter)) to order, and loop over graph[letter], subtracting 1 from inDegree[nextLetter] for each. When a count reaches 0, the next round can pick that letter.
    17. Return order once every letter has been placed.

    The solution in Go

    func alienOrder(words []string) string {
    waiting := make([]bool, 26)
    letters := 0
    for _, word := range words {
        for _, c := range word {
            if !waiting[c - 'a'] {
                waiting[c - 'a'] = true
                letters++
            }
        }
    }
    graph := make([][]int, 26)
    inDegree := make([]int, 26)
    for i := 0; i < len(words) - 1; i++ {
        first := words[i]
        second := words[i + 1]
        j := 0
        for j < len(first) && j < len(second) && first[j] == second[j] {
            j++
        }
        if j < len(first) && j < len(second) {
            graph[first[j] - 'a'] = append(graph[first[j] - 'a'], int(second[j] - 'a'))
            inDegree[second[j] - 'a']++
        } else if len(first) > len(second) {
            return ""
        }
    }
    order := ""
    for len(order) < letters {
        letter := 0
        for letter < 26 && (!waiting[letter] || inDegree[letter] > 0) {
            letter++
        }
        if letter == 26 {
            return ""
        }
        waiting[letter] = false
        order += string(rune('a' + letter))
        for _, nextLetter := range graph[letter] {
            inDegree[nextLetter]--
        }
    }
    return order
}

    The Go details worth a closer look:

    • Runes and bytes. for _, c := range word gives c as a rune (an int32), while first[j] indexes the string and gives a byte (uint8). Both subtract 'a' to give a number from 0 to 25 that can index a slice.
    • The int(...) conversion. graph holds ints, so the byte difference second[j] - 'a' must be converted before append takes it.
    • append returns the grown slice, so it has to be assigned back to graph[first[j] - 'a'].
    • Back to a letter. rune('a' + letter) turns the number into a character, and string(...) turns that character into a string that += can add. string(rune(100)) is "d".
    • Short-circuit order. In the j loop, && keeps first[j] and second[j] from being read past the end of either word.

    Complexity

    Time: O(C). Collecting the letters reads every character once. Comparing neighbouring words reads each word at most twice, once per pair it belongs to. The graph has at most one arrow per pair, so at most n - 1 arrows. Kahn's loop runs at most 26 rounds, each scanning 26 letters and following the arrows of one letter, which is constant work plus the arrows, so it takes O(26 · 26 + n).

    Space: O(1) beyond the arrows. The slices have 26 entries each, and the arrows number at most n - 1. The result has at most 26 letters.

    Edge cases and common mistakes

    • A prefix in the wrong order. ["abc", "ab"] returns "", while ["ab", "abc"] returns "abc".
    • Letters with no arrows. They still belong in the answer. In ["cb", "ca"] the letter c has no arrow, and the answer is "bac", with c last: b is the smallest ready letter at the start, and once it is placed, a becomes ready and is smaller than c.
    • Repeated words. ["z", "z"] gives "z": equal neighbours add no arrow, and the letter is counted once. ["ab", "ab", "ac"] gives "abc".
    • One word. ["a"] gives "a". The loop over pairs doesn't run.
    • A cycle. ["z", "x", "z"] and ["x", "y", "x"] both give "", because the arrows go both ways between two letters.
    • Counting only the letters in arrows. The answer must have every letter that appears, not just those in arrows.
    • Forgetting the smallest-first rule. Taking any ready letter gives a valid order but not necessarily the alphabetically first one.

    Testing

    For ["wrt", "wrf", "er", "ett", "rftt"] the arrows found, in order, are:

    t -> f
w -> e
r -> t
e -> r

    The ready letters at the start are those with no incoming arrow: only w. Then e, r, t and f become ready one at a time, giving "wertf". More inputs, with the results the function returns:

    • ["z", "x", "z"] gives "".
    • ["cb", "ca"] gives "bac".
    • ["abc", "ab"] gives "".
    • ["ba", "bc", "ac", "cab"] gives "bac".
    • ["z", "z"] gives "z".
    • ["a"] gives "a".
    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free