https://leetcode.com/problems/alien-dictionary/

AlienDictionary.java

class Solution {
    public String alienOrder(String[] words) {
        int[] indegree = new int[26];
        Map<Character, Set<Character>> graph = buildGraph(words, indegree);
        System.out.println(String.format("Graph %s", graph));
        System.out.println(String.format("Indegree %s", Arrays.toString(indegree)));
        return topSort(graph, words, indegree);
    }
    
    private String topSort(Map<Character, Set<Character>> graph, String[] words, int[] indegree) {
        
        StringBuilder sb = new StringBuilder();
        Queue<Character> q = new LinkedList<>();
        for(Character c: graph.keySet()) {
            if(indegree[c-'a'] == 0) {
                sb.append(c);
                q.offer(c);
            }
        }
        
        while(!q.isEmpty()) {
            Character curr = q.poll();
            
            if(graph.get(curr)== null || graph.get(curr).isEmpty()) continue;
            for(Character neighbor: graph.get(curr)) {
                indegree[neighbor-'a']--;
                if(indegree[neighbor-'a'] == 0) {
                    sb.append(neighbor);
                    q.offer(neighbor);
                }
            }
        }
        System.out.println(Arrays.toString(indegree));
        System.out.println("Final "+sb.toString());
        return sb.length() == graph.size() ? sb.toString() : "";
        
    }
     
    private Map<Character, Set<Character>> buildGraph(String[] words, int[] indegree) {
        Map<Character, Set<Character>> map = new HashMap<>();
        for(String word: words) {
            for(Character c: word.toCharArray()) {
                map.putIfAbsent(c, new HashSet<>());
            }
        }
        for(int i = 1;i<words.length;i++) {
            String first = words[i-1];
            String second = words[i];
            for(int j = 0;j<Math.min(first.length(), second.length()); j++) {
                if(first.charAt(j)!=second.charAt(j)) {
                    if(!map.get(first.charAt(j)).contains(second.charAt(j))) {
                        indegree[second.charAt(j)-'a']++;
                        map.get(first.charAt(j)).add(second.charAt(j));    
                    }
                    
                }
            }
        }
        
        return map;
    }
    
}