Java Topology Sort - Clean and Understandable


  • 1
    B
    public class Solution {
        public String alienOrder(String[] words) {
            if(words == null || words.length == 0) return "";
            if(words.length == 1) return words[0];
            
            Map<Character, Set<Character>> map = new HashMap<Character, Set<Character>>();
            int[] indegree = new int[26];
            int len = words.length;
            for(int i = 0; i < len - 1; i++) {
                // corner case
                if(words[i].startsWith(words[i+1]) && words[i].length() > words[i+1].length()) return ""; 
                generateDependency(map, indegree, words[i], words[i+1]);
            }
            String order = topologySort(map, indegree);
            if(order.length() != map.size()) return "";
            return order;
        }
        
        private void generateDependency(Map<Character, Set<Character>> map, int[] indegree, String w1, String w2) {
            for(int i = 0;i < w1.length(); i++) {
                if(!map.containsKey(w1.charAt(i))) {
                    map.put(w1.charAt(i), new HashSet<Character>());
                }
            }
            for(int i = 0; i < w2.length(); i++) {
                if(!map.containsKey(w2.charAt(i))) {
                    map.put(w2.charAt(i), new HashSet<Character>());
                }
            }
            for(int i = 0; i < w1.length() && i < w2.length(); i++) {
                char c1 = w1.charAt(i);
                char c2 = w2.charAt(i);
                if(c1 != c2) {
                    if(map.get(c1).add(c2)) {
                        indegree[c2-'a']++;
                    }
                    return;
                }
            }
            
        }
        
        private String topologySort(Map<Character, Set<Character>> map, int[] indegree) {
            Queue<Character> queue = new LinkedList<Character>();
            for(Map.Entry<Character, Set<Character>> p: map.entrySet()) {
                if(indegree[p.getKey() - 'a'] == 0) {
                    queue.add(p.getKey());
                }
            }
            
            StringBuilder order = new StringBuilder();
            while(!queue.isEmpty()) {
                char curr = queue.poll();
                order.append(curr);
                for(char next: map.get(curr)) {
                    if(--indegree[next-'a'] == 0) {
                        queue.add(next);
                    }
                }
            }
            return order.toString();
        }
        
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.