Start learning free

LESSON 481 OF 541 · GRAPHS

Alien Dictionary in Swift: Topological Sort in O(C) Time

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

    SWIFT · GRAPHS

    Alien Dictionary in Swift, explained

    Problem overview

    An alien language uses the lowercase English letters in an unknown order. The method alienOrder receives words, a list sorted in that alien alphabetical order, and returns a string holding every letter that appears in the words, once each, in the alien order. Words are compared as in any dictionary: at the first position where they differ, the word with the earlier letter comes first, and when one word is a prefix of the other, the shorter one comes first. 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 alphabet, which makes the answer unique.

    For ["wrt", "wrf", "er", "ett", "rftt"] the answer is "wertf". For ["z", "x", "z"] it is "": "z" before "x" says z comes first, and "x" before "z" says the opposite. For ["cb", "ca"] it is "bac": the words differ at the second letter, so b comes before a, and c is free. The orders "bac", "bca" and "cba" all work, and "bac" is first alphabetically.

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

    Approach: turn neighbouring words into arrows

    Each pair of neighbouring words gives at most one fact: at the first position where they differ, the letter of the first word comes before the letter of the second. Comparing neighbours is enough. If every word is in order with the next one, the whole list is sorted, so other pairs add nothing new. Letters after the first difference tell us nothing.

    For the first example the neighbouring pairs give these arrows:

    wrt wrf t -> f
wrf er w -> e
er ett r -> t
ett rftt e -> r

    Chained together: w, e, r, t, f.

    The task is now a topological sort of a graph whose nodes are letters and whose arrows say "must come before". A letter can be placed once every letter that must come before it is already placed. Count the arrows coming into each letter (its in-degree). A letter with count 0 that hasn't been placed is ready. Place a ready letter, then lower the count of every letter it points to. This is Kahn's algorithm. To get the alphabetically smallest valid order, take the smallest ready letter in each round.

    There are two ways to contradict yourself. One is a cycle among the letters: some letters are still waiting but none is ready. The other is a word followed by its own proper prefix, such as ["abc", "ab"]: the shorter word must come first in any alphabet, so the answer is "".

    Comparing every pair of words instead of neighbours would take O(n²) comparisons for n words.

    Step by step

    1. Create waiting as 26 false values, one per letter. waiting[k] is true while letter number k appears in the words but isn't in the answer yet. With only 26 letters, an array is simpler than a dictionary.
    2. Create letters at 0, the number of different letters. The answer is complete when it has that many characters.
    3. Loop over each word.
    4. Loop over each byte c in word.utf8. The codes of a to z are 97 to 122.
    5. Test !waiting[Int(c) - 97]. Int(c) - 97 is 0 for a, 1 for b, up to 25 for z.
    6. Mark the letter by setting its waiting entry to true.
    7. Add 1 to letters. The if ensures each letter is counted once.
    8. Create graph as 26 empty arrays. graph[a] holds the letters that must come after a. Arrays are values, so each letter gets its own array.
    9. Create inDegree as 26 zeros.
    10. Loop i over 0..<words.count - 1, the neighbouring pairs.
    11. Turn the pair into byte arrays, first and second, because a String can't be indexed with an integer.
    12. Start j at 0 to find the first position where they differ.
    13. Loop while j is inside both words and the bytes are equal. The checks run left to right, so the bytes are read only while j is in range.
    14. Add 1 to j.
    15. If j is still inside both words, first[j] and second[j] are the first different letters.
    16. Append the arrow: second[j]'s index goes into graph at first[j]'s index.
    17. Add 1 to the in-degree of second[j]. Two pairs can give the same arrow. Each copy is counted here and removed once later.
    18. Otherwise, else if first.count > second.count: the second word is a prefix of the first, so return "". An equal or shorter first word gives no fact.
    19. Create order as an empty string.
    20. Loop while order.count < letters. Each round places one letter.
    21. Start letter at 0. It walks from a to z.
    22. Skip letters that aren't ready: while letter < 26 and the letter isn't waiting or still has arrows coming in.
    23. Add 1 to letter inside that loop. The first ready letter is the smallest, which is what makes the answer alphabetically first.
    24. If letter == 26, nothing is ready while letters still wait: a cycle. Return "".
    25. Place the letter: set its waiting entry to false.
    26. Append it to order. Character(UnicodeScalar(UInt8(97 + letter))) turns the index back into a letter.
    27. Loop over graph[letter], the letters that must come after it.
    28. Subtract 1 from each one's in-degree. When it reaches 0, the next round finds it ready.
    29. Return order.

    The solution in Swift

    class Solution {
    func alienOrder(_ words: [String]) -> String {
        var waiting = [Bool](repeating: false, count: 26)
        var letters = 0
        for word in words {
            for c in word.utf8 {
                if !waiting[Int(c) - 97] {
                    waiting[Int(c) - 97] = true
                    letters += 1
                }
            }
        }
        var graph = [[Int]](repeating: [], count: 26)
        var inDegree = [Int](repeating: 0, count: 26)
        for i in 0..<words.count - 1 {
            let first = Array(words[i].utf8)
            let second = Array(words[i + 1].utf8)
            var j = 0
            while j < first.count && j < second.count && first[j] == second[j] {
                j += 1
            }
            if j < first.count && j < second.count {
                graph[Int(first[j]) - 97].append(Int(second[j]) - 97)
                inDegree[Int(second[j]) - 97] += 1
            } else if first.count > second.count {
                return ""
            }
        }
        var order = ""
        while order.count < letters {
            var letter = 0
            while letter < 26 && (!waiting[letter] || inDegree[letter] > 0) {
                letter += 1
            }
            if letter == 26 {
                return ""
            }
            waiting[letter] = false
            order.append(Character(UnicodeScalar(UInt8(97 + letter))))
            for nextLetter in graph[letter] {
                inDegree[nextLetter] -= 1
            }
        }
        return order
    }
}

    The Swift details worth a closer look:

    • Bytes instead of characters. word.utf8 yields each byte as a UInt8. For lowercase English letters one byte is one letter, so Array(words[i].utf8) gives an array you can index with an integer.
    • Convert to Int before subtracting. Int(c) - 97 works on 64-bit integers. Subtracting on the UInt8 itself is dangerous: UInt8 can't be negative, so a result below 0 traps and the program crashes.
    • Back to a character. UInt8(97 + letter) is the byte, UnicodeScalar(...) makes a Unicode scalar from it, and Character(...) makes a character that append accepts.
    • Nested arrays. [[Int]](repeating: [], count: 26) makes 26 independent empty arrays, because arrays are value types and are copied when they change.
    • Counting characters. order.count counts characters. It is cheap enough here because the answer has at most 26 letters.
    • && and || short-circuit. In the while conditions the range test comes first, so waiting[letter] is never read with letter == 26.

    Complexity

    Time: O(C), where C is the total number of letters. Reading all letters is O(C). Comparing neighbouring words takes at most the length of the shorter word per pair, so O(C) overall. The ordering loop places at most 26 letters and scans at most 26 candidates for each, plus the arrows, a constant amount of work.

    Space: O(1) beyond the input. The arrays have 26 entries, and there are at most one arrow per neighbouring pair. Counting those arrows, the space is O(n) for n words.

    Edge cases and common mistakes

    • A word followed by its prefix. ["abc", "ab"] returns "", while ["ab", "abc"] returns "abc".
    • Cycles. ["ab", "ba", "ac"] gives a before b and b before a, so it returns "". ["a", "b", "a"] does the same.
    • Letters without any fact. In ["cb", "ca"], c has no arrows but must still be in the answer: "bac". This is why the code collects letters from all words, not only from arrows.
    • A single word. ["z"] returns "z". 0..<words.count - 1 is the empty range 0..<0, so the pair loop does nothing.
    • Duplicates. ["z", "z"] returns "z": equal words give no fact and are not contradictory.
    • Taking any ready letter. The answer must be the alphabetically first order, so each round takes the smallest ready letter. For ["ba", "bc", "ac", "cab"] the result is "bac".
    • Using more than the first difference. Only the first differing position of a pair gives a fact. Later letters give none.

    Testing

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