Start learning free

LESSON 483 OF 543 · GRAPHS

Alien Dictionary in Rust: Topological Sort on 26 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

    RUST · GRAPHS

    Alien Dictionary in Rust, explained

    Problem overview

    An alien language uses the lowercase English letters in an order you don't know. The function alien_order receives words, a vector of strings sorted in that alien alphabetical order. It returns a string with every letter that appears in the words, each once, 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. When one word is a prefix of the other, the shorter one comes first, so "ab" comes before "abc". If the words contradict themselves, so that no order of the letters makes them sorted, the function 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 "", because the list says z comes before x and also x before z. For ["cb", "ca"] it is "bac": the words only tell us that b comes before a, and of the orders "bac", "bca" and "cba", the first is alphabetically smallest.

    Approach: turn neighbouring words into arrows

    Each pair of neighbouring words gives at most one fact, found at the first position where they differ: the letter in the first word comes before the letter in the second. Letters after that position tell us nothing. If every word is in order with the next one, the whole list is sorted, so neighbours are enough. Comparing every pair would take far more work for no new facts.

    For the first example, the four pairs give:

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

    Chained together, that is w, e, r, t, f.

    These arrows form a graph on the letters, and an order that respects every arrow is a topological order. Kahn's algorithm finds one: repeatedly place a letter that has no unplaced letter required before it, then remove its arrows. To get the alphabetically first answer, each round takes the smallest letter that is ready. If at some point letters remain but none is ready, they wait for each other in a cycle, and the answer is "".

    There is one more contradiction that arrows can't show: a word that comes before its own prefix, such as ["abc", "ab"]. There is no differing letter, but the longer word is first, so no alphabet can sort the list.

    Running the pairs of ["cb", "ca"] gives the single arrow b to a, and the letters are placed as b, then a, then c. The letter c is placed last because a is smaller and becomes ready first.

    Step by step

    1. Mark the letters that appear. waiting is a vector of 26 false values, one per letter. An array indexed by letter is simpler than a dictionary when there are only 26 possibilities. waiting[k] will be true while letter number k appears in the words and isn't in the answer yet.
    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 and then over each of its bytes c. The expression c - b'a' is 0 for a, 1 for b and so on to 25 for z, and as usize makes it an index.
    4. Count each letter once: when !waiting[...] is true, set the entry to true and add 1 to letters.
    5. Create the graph as a Vec<Vec<usize>> of 26 empty vectors with vec![Vec::new(); 26]. graph[a] holds the letters that must come after letter a.
    6. Create in_degree, 26 zeros. in_degree[b] counts the letters that must come before b and aren't placed yet.
    7. Loop over the neighbouring pairs with i in 0..words.len() - 1, and take the bytes of words[i] and words[i + 1] with as_bytes(), since a String can't be indexed by position.
    8. Find the first difference: start j at 0 and advance it while it is inside both words and the bytes are equal. The checks run left to right and stop at the first one that fails, so the bytes are read only while j is in range for both.
    9. If j is still inside both words, the two bytes there are the first letters that differ. Push the second letter onto the first letter's list in graph, and add 1 to the second letter's in_degree. Two pairs may give the same arrow. Each copy is counted here and removed once later, so that is fine.
    10. Otherwise, if the first word is longer (} else if first.len() > second.len()), the second word is a prefix of the first and should have come first. Return String::new(). A first word that is shorter or equal gives no fact.
    11. Create order as an empty String and loop while order.len() < letters. Each round places one letter.
    12. Find the smallest ready letter. Start letter at 0 and advance it while letter < 26 and the letter isn't waiting or still has arrows coming in. A ready letter appears in the words, isn't placed yet, and has all the letters before it placed.
    13. Detect a cycle. If letter == 26, no letter is ready, so the remaining ones wait on each other. Return String::new().
    14. Place the letter. Set waiting[letter] to false and push (b'a' + letter as u8) as char onto order. The index becomes a byte so it can be added to b'a', and as char turns the byte into a character.
    15. Release the letters after it. For each next_letter in &graph[letter], subtract 1 from its in_degree.
    16. Return order without a semicolon.

    The solution in Rust

    impl Solution {
    fn alien_order(words: Vec<String>) -> String {
        let mut waiting = vec![false; 26];
        let mut letters = 0;
        for word in &words {
            for c in word.bytes() {
                if !waiting[(c - b'a') as usize] {
                    waiting[(c - b'a') as usize] = true;
                    letters += 1;
                }
            }
        }
        let mut graph: Vec<Vec<usize>> = vec![Vec::new(); 26];
        let mut in_degree = vec![0; 26];
        for i in 0..words.len() - 1 {
            let first = words[i].as_bytes();
            let second = words[i + 1].as_bytes();
            let mut j = 0;
            while j < first.len() && j < second.len() && first[j] == second[j] {
                j += 1;
            }
            if j < first.len() && j < second.len() {
                graph[(first[j] - b'a') as usize].push((second[j] - b'a') as usize);
                in_degree[(second[j] - b'a') as usize] += 1;
            } else if first.len() > second.len() {
                return String::new();
            }
        }
        let mut order = String::new();
        while order.len() < letters {
            let mut letter = 0;
            while letter < 26 && (!waiting[letter] || in_degree[letter] > 0) {
                letter += 1;
            }
            if letter == 26 {
                return String::new();
            }
            waiting[letter] = false;
            order.push((b'a' + letter as u8) as char);
            for &next_letter in &graph[letter] {
                in_degree[next_letter] -= 1;
            }
        }
        order
    }
}

    The Rust details worth a closer look:

    • Bytes as letters. word.bytes() yields u8 values, and b'a' is the u8 code of the letter a. Subtracting gives a u8, and as usize makes it an index. The subtraction can't underflow, because the words hold only lowercase letters.
    • Inferred types. letters and in_degree name no integer type. Both default to i32, except that letters is compared with order.len(), which makes it a usize. And letter is a usize, because it indexes vectors.
    • vec![Vec::new(); 26]. The macro clones the value for every entry, so each letter gets its own empty vector, not one shared vector. The type on graph tells the compiler what the vectors hold.
    • &words and &graph[letter]. The & borrows instead of moving. The pattern &next_letter in the last loop copies each usize out of the reference.
    • (b'a' + letter as u8) as char. The cast letter as u8 binds tighter than +. A u8 can be cast to char directly, and push appends a character to the String.
    • String::len() counts bytes. For the lowercase letters here, bytes and characters are the same, so order.len() is the number of letters placed.
    • words.len() - 1. The length is a usize, so for an empty vector the subtraction would underflow. The constraints promise at least one word. With exactly one word the range 0..0 is empty and the loop doesn't run.

    Complexity

    Time: O(C), where C is the total number of letters in words. Reading every letter takes O(C). Each neighbouring pair is compared up to the length of the shorter word, which is at most C in total. The placing loop runs at most 26 rounds, each scanning 26 letters and releasing the arrows of one letter. The number of different arrows is bounded by the pairs, so the placing loop is constant work for the fixed alphabet.

    Space: O(1) beyond the input, plus the arrows. The vectors have 26 entries each, and the arrows are at most one per neighbouring pair, so the graph holds at most n - 1 entries for n words.

    Edge cases and common mistakes

    • A word before its own prefix. ["abc", "ab"] returns "". Without the else if branch, the pair would add no arrow and the function would return "abc".
    • A prefix after its word. ["ab", "abc"] is fine and returns "abc", since the shorter word comes first.
    • A cycle. ["z", "x", "z"] gives the arrows z to x and x to z. Neither letter ever has in_degree 0, so letter reaches 26 and the function returns "". The list ["a", "b", "a"] does the same.
    • Letters with no arrows. In ["cb", "ca"], the letter c is in no arrow. It is still in the answer, and it is placed when it is the smallest ready letter.
    • Repeated words. ["z", "z"] gives no arrow, because the words are equal, and returns "z".
    • Counting letters that don't appear. Only letters found in the words are placed. The waiting vector keeps unused letters out of the answer.
    • Taking any ready letter. The answer must be the alphabetically first order, so each round scans from a upward and takes the first ready letter. A stack or queue of ready letters may give a different valid order.
    • Comparing non-neighbours. Looking only at neighbouring words is enough, because the order is transitive.

    Testing

    • ["wrt", "wrf", "er", "ett", "rftt"] gives "wertf".
    • ["z", "x", "z"] gives "".
    • ["cb", "ca"] gives "bac".
    • ["abc", "ab"] gives "".
    • ["ab", "abc"] gives "abc".
    • ["z"] gives "z".
    • ["z", "z"] gives "z".
    • ["za", "zb", "ab", "eb", "ec"] gives "zabce".
    • ["ba", "bc", "ac", "cb"] gives "bac".
    • ["ab", "ac", "bc", "bd"] gives "abcd".
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free