Start learning free

LESSON 480 OF 540 · GRAPHS

Alien Dictionary in Scala: 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 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

    SCALA · GRAPHS

    Alien Dictionary in Scala, explained

    Problem overview

    The method alienOrder(words: Array[String]): String receives words from an alien dictionary. The alien language uses the lowercase English letters, but in an order you do not know, and the words are sorted in that order. Words compare as in any dictionary: at the first position where they differ, the word with the earlier letter comes first, and a word that is a prefix of another comes first, so "ab" always precedes "abc".

    The method returns every letter that appears in words, each once, in alien order. If the words contradict themselves, so that no order makes them sorted, it returns "". When several orders work, it returns the one that comes first in the usual alphabet, which makes the answer unique.

    For Array("wrt", "wrf", "er", "ett", "rftt") the answer is "wertf". For Array("z", "x", "z") it is "": "z" before "x" says z comes first, and "x" before "z" says x comes first. For Array("cb", "ca") the answer is "bac": the words only tell us that b comes before a, the orders "bac", "bca" and "cba" all work, and "bac" is the first alphabetically.

    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. Letters after that position say nothing. Neighbouring pairs are enough, because if every word is in order with the next one, the whole list is sorted.

    For the first example the four pairs give:

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

    Chained, these facts say w, e, r, t, f. For "cb" and "ca" the only fact is b before a.

    Each fact is an arrow between two letters. An order that agrees with every arrow is a topological order, and Kahn's algorithm finds one: keep an in-degree for every letter, the number of unplaced letters that must come before it, and repeatedly place a letter whose in-degree is 0. Taking the alphabetically smallest ready letter each time gives the answer the statement asks for. If at some point no letter is ready but some are still waiting, they wait on one another: a cycle, so the answer is "".

    One more contradiction does not show up as an arrow: if the first word is longer than the second and the second is a prefix of it, no alphabet can sort them. Array("abc", "ab") returns "".

    The work is proportional to the total number of letters in the words, O(C), since neighbouring words are compared once. Comparing every pair of words would take O(n²) comparisons.

    Step by step

    1. Find the letters that appear. Create waiting as Array.fill(26)(false), one flag per letter. waiting(k) is true while letter number k appears in the words and is not yet in the answer. With only 26 letters, an array indexed by letter is simpler than a map.
    2. Count the different letters in a var letters starting at 0. The answer is complete when its length reaches this count.
    3. Loop over each word and each character c. If !waiting(c - 'a'), set it to true and add 1 to letters. Subtracting two Chars gives an Int, so c - 'a' is 0 for a and 25 for z. The if counts each letter the first time it appears.
    4. Build the graph as Array.fill(26)(mutable.ArrayBuffer[Int]()). graph(a) holds the letters that must come after letter a. Array.fill evaluates its second argument once per element, so each letter gets its own buffer.
    5. Create inDegree as Array.fill(26)(0). inDegree(b) counts the unplaced letters that must come before b.
    6. Loop over neighbouring pairs with i <- 0 until words.length - 1, naming words(i) as first and words(i + 1) as second.
    7. Find the first difference. A var j starts at 0 and a while loop advances it while j is inside both words and first(j) == second(j). The checks run left to right and stop at the first false one, so the characters are read only while j is valid.
    8. If j is still inside both words, the letters at j are the first that differ. Append second(j) - 'a' to graph(first(j) - 'a') with +=, and add 1 to inDegree(second(j) - 'a'). Two pairs can give the same arrow; each copy is counted here and removed once later.
    9. Otherwise, if first.length > second.length, return "": the second word is a prefix of the first and should come first in any alphabet. A shorter or equal first word gives no fact.
    10. Collect the answer in a var order that starts as an empty string, and loop while order.length < letters. Each round places one letter.
    11. Find the smallest ready letter. Start a var 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. The first letter that stops the loop is the alphabetically smallest ready one.
    12. If letter == 26, no letter is ready although some are waiting: return "".
    13. Place the letter. Set waiting(letter) to false and append ('a' + letter).toChar to order. 'a' + letter is an Int, and toChar turns it back into a letter, so += adds a letter and not a number.
    14. Release its neighbours. For each nextLetter in graph(letter), subtract 1 from inDegree(nextLetter). When a count reaches 0, the next round finds that letter ready.
    15. Return order once every letter is placed.

    The solution in Scala

    class Solution {
    def alienOrder(words: Array[String]): String = {
        val waiting = Array.fill(26)(false)
        var letters = 0
        for (word <- words) {
            for (c <- word) {
                if (!waiting(c - 'a')) {
                    waiting(c - 'a') = true
                    letters += 1
                }
            }
        }
        val graph = Array.fill(26)(mutable.ArrayBuffer[Int]())
        val inDegree = Array.fill(26)(0)
        for (i <- 0 until words.length - 1) {
            val first = words(i)
            val second = words(i + 1)
            var j = 0
            while (j < first.length && j < second.length && first(j) == second(j)) {
                j += 1
            }
            if (j < first.length && j < second.length) {
                graph(first(j) - 'a') += second(j) - 'a'
                inDegree(second(j) - 'a') += 1
            } else if (first.length > second.length) {
                return ""
            }
        }
        var order = ""
        while (order.length < letters) {
            var letter = 0
            while (letter < 26 && (!waiting(letter) || inDegree(letter) > 0)) {
                letter += 1
            }
            if (letter == 26) {
                return ""
            }
            waiting(letter) = false
            order += ('a' + letter).toChar
            for (nextLetter <- graph(letter)) {
                inDegree(nextLetter) -= 1
            }
        }
        return order
    }
}

    The Scala details worth a closer look:

    • Char arithmetic. 'd' - 'a' is the Int 3. 'a' + 3 is the Int 100, and ('a' + 3).toChar is 'd'. Adding the Int directly to a String would append digits instead of a letter.
    • mutable.ArrayBuffer is a growable list, and += appends to it. The lesson provides mutable; in a file of your own, add import scala.collection.mutable.
    • Array.fill(26)(mutable.ArrayBuffer[Int]()) creates 26 separate buffers, because the second argument is evaluated for every element. Appending to graph(0) leaves graph(1) empty.
    • for (c <- word) walks the characters of a String directly.
    • String building. order += ... on a var of type String makes a new string each time. With at most 26 letters that cost does not matter.
    • return inside loops. Early exits use return "". Those inside a for body are non-local returns, which Scala 3.5 accepts but warns about. The returns in the while loops are ordinary.

    Complexity

    Time: O(C), where C is the total number of letters in words. Counting letters touches each letter once, and comparing neighbouring words touches each letter at most twice. The placing loop does at most 26 rounds, each scanning 26 letters and releasing the arrows of one letter, so it costs a constant plus the number of arrows, which is at most the number of word pairs.

    Space: O(n) in the number of words n, at worst. The arrays have 26 entries each. The buffers together hold one entry per recorded arrow, and each neighbouring pair of words records at most one.

    Edge cases and common mistakes

    • A word that is a prefix after its extension. Array("abc", "ab") gives "", and so does Array("ab", "a"). In the other order, Array("ab", "abc") gives no fact and is fine.
    • A cycle. Array("z", "x", "z") and Array("a", "b", "a") give "": no letter is ever ready.
    • A repeated word. Array("z", "z") gives "z". Equal neighbours say nothing.
    • One word. Array("a") gives "a": no pairs, one letter, placed in the first round.
    • Letters with no facts. In Array("c", "a", "b") the facts are c before a and a before b, so the answer is "cab". In Array("ab", "adc") the single fact is b before d, and the answer is "abcd", with each unconstrained letter in its alphabetical place.
    • Forgetting letters that never appear in a fact. Every letter of every word must be in the answer. Counting letters first, and not only those in arrows, is what guarantees it.
    • Not taking the smallest ready letter. Any ready letter gives a valid order, but only the smallest gives the order the statement asks for.
    • Sharing one buffer. Filling the graph with one buffer repeated would make every letter's neighbours the same list.

    Testing

    • Array("wrt", "wrf", "er", "ett", "rftt") gives "wertf".
    • Array("z", "x", "z") gives "".
    • Array("cb", "ca") gives "bac".
    • Array("abc", "ab") gives "".
    • Array("z", "z") gives "z".
    • Array("a") gives "a".
    • Array("ab", "adc") gives "abcd".
    • Array("ba", "bc", "ac", "cab") gives "bac".
    • Array("abc", "abd", "b") gives "abcd".
    • Array("x", "y", "z") gives "xyz".
    • Array("c", "a", "b") gives "cab".
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free