Alien Dictionary - Teeeeeebag/LeetCode GitHub Wiki

public class Solution {
    public String alienOrder(String[] words) {
        if(words.length == 0){
            return "";
        }
        HashMap<Character, HashSet<Character>> adjList = new HashMap<>();
        HashMap<Character, Integer> outdegree = new HashMap<>();
        HashSet<Character> characters = new HashSet<>();
        for (int i=0; i<words.length-1; ++i){
            int len = Math.min(words[i].length(), words[i+1].length());
            for(int k=0; k<len; ++k){
                if(k==0 || words[i].substring(0, k).equals(words[i+1].substring(0, k))){
                    char smaller = words[i].charAt(k), larger = words[i+1].charAt(k);
                    if (smaller == larger){
                        continue;
                    }
                    if(!outdegree.containsKey(smaller)){
                        outdegree.put(smaller, 0);
                    }
                    if (!adjList.containsKey(larger)){
                        adjList.put(larger, new HashSet());
                    }
                    if (!adjList.get(larger).contains(smaller)){
                        outdegree.put(smaller, outdegree.get(smaller)+1);
                        adjList.get(larger).add(smaller);
                    }
                }
            }
        }
        LinkedList<Character> queue = new LinkedList<>();
        for (int i=0; i<words.length; ++i){
            for (char ch : words[i].toCharArray()){
                characters.add(ch);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (Character ch : characters){
            if(!outdegree.containsKey(ch)){
                queue.add(ch);
                sb.append(ch);
            }
        }
        while(!queue.isEmpty()){
            char head = queue.getFirst();
            queue.removeFirst();
            HashSet<Character> adjs = adjList.get(head);
            if(adjs!=null){
                for (Character ch : adjs){
                    outdegree.put(ch, outdegree.get(ch)-1);
                    if (outdegree.get(ch) == 0){
                        queue.add(ch);
                        sb.append(ch);
                        outdegree.remove(ch);
                    }
                }
            }
            
        }
        if (outdegree.isEmpty()){
            return sb.reverse().toString();
        } else {
            return "";
        }
    }
}