Alien Dictionary

Problem

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
The correct order is: "wertf".

Example 2:
Given the following words in dictionary,

[
  "z",
  "x"
]
The correct order is: "zx".

Example 3:
Given the following words in dictionary,

[
  "z",
  "x",
  "z"
]
The order is invalid, so return "".

Note:

• You may assume all letters are in lowercase.
• You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
• If the order is invalid, return an empty string.
• There may be multiple valid order of letters, return any one of them is fine.

Solution

Topological Sort and Hash Table Solution

class Solution {
    public String alienOrder(String[] words) {
        if (words == null || words.length == 0) return "";
        //get Degrees 
        int[] degrees = new int[26];
        for (String word : words) {
            for (char ch : word.toCharArray()) degrees[ch - 'a'] = 1;
        }
        int count = 0;
        for (int degree: degrees) if (degree == 1)  count++;

        //get maps 
        Map<Character, Set<Character>> map = new HashMap<>();
        for (int i = 0; i < words.length - 1; i++) {
            String cur = words[i], next = words[i + 1];
            int min = Math.min(cur.length(), next.length());
            for (int j = 0; j < min; j++) {
                char c1 = cur.charAt(j), c2 = next.charAt(j);
                if (c1 != c2) {
                    Set<Character> set = map.getOrDefault(c1, new HashSet<>());
                    if (set.add(c2)) {
                        degrees[c2 - 'a']++;
                        map.put(c1, set);
                    }
                    break; //We just need first diff char, others aren't useful
                }
            }
        }

        //Topological sort 
        Queue<Character> q = new LinkedList<>();
        for (int i = 0; i < 26; i++) {
            if (degrees[i] == 1) q.offer((char) (i + 'a'));
        }
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            char cur = q.poll();
            sb.append(cur);
            for (char ch : map.getOrDefault(cur, new HashSet<>())) {
                if (--degrees[ch - 'a'] == 1) q.offer(ch);
            }
        }
        return sb.length() == count ? sb.toString() : "";
    }
}

Analysis

This solution is divided into three steps as comments indicate

The first step is to store degrees of each existing character
We use int[26] to store degree of each existing character from the given dictionary
Since the default value of array is 0 we use 1 to degree 0, 2 to degree 1, etc.
We also need to have a var to count total existing character to check whether we have valid order after the topological sort

The second step is to compare each word with its right next word
We need to find the first different character between these two words to decide the correct order
We need to break immediately after we found a first difference, cause the orders of left characters won't make sense since their previous characters are already different
We use a Map<Character, Set<Character>> to store each character as key and its following character as value
If the second char has not been appeared in the first char's following characters
We add it to the set, and increase the degree of the second char

The third step is to apply topological sort to get correct order
As mentioned above, we use 1 to indicate non degree character, hence we offer all character whose degree is 1
Then we use StringBuilder to collect characters in order and offer char to the queue if its degree becomes 1
At the end, we need to check if sb.length() == count, to see if we have valid order after topological sort