My Concise and Self-Understanding Solution base on @jinwu


  • 0
    A
    public class Solution {
        Set<Character> charSet = new HashSet<>(); 
        Map<Character, List<Character>> graph = new HashMap<>();
        Map<Character, Integer> indegree = new HashMap<>(); // the number of in degree for each vertex
        
        public String alienOrder(String[] words) {
            // first we find all the vertex 
            getCharSet(words);
            for(Character v: charSet) {
                graph.put(v, new ArrayList<Character>());
                indegree.put(v , 0);
            }
            // then we build a graph
            buildGraph(words);
            return  topologicSort(graph); // then topologicSort
        }
        
        private void getCharSet(String[] words) {
            for (String word : words) {
                for (char c : word.toCharArray()) {
                    charSet.add(c);
                }
            }
        }
    
        
        private void buildGraph(String[] words) {
             for (int i = 0; i < words.length - 1; i++) {
                for (int j = i + 1; j < words.length; j++) {
                    for (int k = 0; k < Math.min(words[i].length(), words[j].length()); k++) {
                        char first = words[i].charAt(k);
                        char second =  words[j].charAt(k);
                        if (first  != second) {
                            List<Character> adjList = graph.get(first);
                            if (!adjList.contains(second))
                                graph.get(first).add(second);
                             
                            break;
                        }
                    }
                }
            }
        }
        
        private String topologicSort(Map<Character, List<Character>> graph) {
             for(Character v: graph.keySet()) {
                List<Character> adj = graph.get(v);
                for(char u: adj) {
                    indegree.put(u, indegree.get(u) + 1);
                }
            }
            
            Queue<Character> q = new LinkedList<>();
            StringBuffer sb = new StringBuffer();
            for(Character c: indegree.keySet()) {
                if(indegree.get(c) == 0) {
                    q.add(c);
                    
                }
            }
    
            while(!q.isEmpty()) {
                char v = q.poll();
                sb.append(v);
                indegree.remove(v);
                List<Character> adj = graph.get(v);
                System.out.println(adj);
                for(Character u: adj) {
                    indegree.put(u, indegree.get(u) - 1);
                    if(indegree.get(u) == 0) {
                        q.add(u);
                        
                    }   
                }
            }
            if(indegree.keySet().isEmpty()) {
                return sb.toString();
            } else {
                return "";
            }
    
        }
    }

Log in to reply
 

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