269. Alien Dictionary

Published on April 21, 2023

Question

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.

Algorithm

Read question carefully. I firstly made a mistake. It said the words are sorted lexicographically. I'm not careful and think it's the characters in each word are sorted lexicographically.
Others thing are much similar to the course schedule, a typical topological sorting question.
Here you have no edges or graph to be traversed, so you have to construct by yourself. Compare adjacent words and find the first not equal character, then you get a dependency relation.
A few things to notice is that:
1. If the previous string is longer than the latter one and the latter one is also a prefix of the former, this violate the whole dictionary(all the words) are sorted lexicographically, and thus we return empty string.
2. Once you a getting a different character, the following are useless and you should stop here when comparing.
3. Ultimately, you should compare if the length of in degree(number of characters ) is equal to the size of result. If not, it mean we have come repeat character or we have a cycle here. Return an empty string is desired. Otherwise return a valid lexicographically sorting.

Code

class Solution {
    public String alienOrder(String[] words) {
        StringBuilder sb = new StringBuilder();
        if (words == null || words.length == 0) {
            return sb.toString();
        }
        
        Map<Character, Set<Character>> prerequisites = new HashMap<>();
        Map<Character, Integer> indegree = new HashMap<>();
        for (String word : words) {
            for (Character ch : word.toCharArray()) {
                indegree.put(ch, 0);
            }
        }
        
        for (int i = 0; i < words.length - 1; i++) {
            String word1 = words[i];
            String word2 = words[i + 1];
            int len = Math.min(word1.length(), word2.length());
            if (word1.length() != word2.length() && word1.startsWith(word2)) return ""; // notice
            for (int j = 0; j < len; j++) {
                if (word1.charAt(j) != word2.charAt(j)) { // notice
                    Set<Character> set = prerequisites.getOrDefault(word1.charAt(j), new HashSet<>());
                    if (!set.contains(word2.charAt(j))) {
                        set.add(word2.charAt(j));
                        indegree.put(word2.charAt(j), indegree.get(word2.charAt(j)) + 1);
                    }
                    prerequisites.put(word1.charAt(j), set);
                    
                    break; // notice
                }
            }
        }
        
        
        
        Queue<Character> queue = new LinkedList<>();
        for (Character ch : indegree.keySet()) {
            if (indegree.get(ch) == 0) {
                queue.offer(ch);
            }
        }
        
        while (!queue.isEmpty()) {
            Character cur = queue.poll();
            sb.append(cur);
            if (prerequisites.containsKey(cur)) {
                for (Character ch : prerequisites.get(cur)) {
                    indegree.put(ch, indegree.get(ch) - 1);
                    if (indegree.get(ch) == 0) {
                        queue.offer(ch);
                    }
                }
                
            }
        }
        
        return sb.length() == indegree.size() ? sb.toString() : ""; // notice
    }
}