9 ms Java solution based on DFS with detailed comments


  • 0
    S
    class Solution {
        public String alienOrder(String[] words) {
            // Build a graph in which an edge from A to B indicates that A appears before B in the alphabet
            Map<Character, Set<Character>> graph = new HashMap<Character, Set<Character>>();
            // Add all nodes
            for(String word : words) {
                for(Character node : word.toCharArray()) {
                    if(!graph.containsKey(node)) {
                        graph.put(node, new HashSet<Character>());
                    }
                }    
            }
            // Add the edges
            for(int i = 0; i < words.length - 1; i++) {
                String w1 = words[i];
                String w2 = words[i + 1];
                int minLength = Math.min(w1.length(), w2.length());
                int j = 0;
                while(j < minLength && w1.charAt(j) == w2.charAt(j)) {
                    j++;
                }
                if(j < minLength) {
                    graph.get(w1.charAt(j)).add(w2.charAt(j));
                }
            }
            // Perform a topological sorting based on DFS.
            StringBuilder sb = new StringBuilder();
            Set<Character> visited = new HashSet<Character>();
            Set<Character> ancestors = new HashSet<Character>();
            for(char node : graph.keySet()) {
                if(!visited.contains(node)) {
                    if(!DFS(node, graph, visited, ancestors, sb)) {
                        return "";
                    };
                }
            }
            return sb.toString();
        }
        
        private Boolean DFS(char root, Map<Character, Set<Character>> graph, Set<Character> visited, Set<Character> ancestors, StringBuilder sb)     {
            if(ancestors.contains(root)) {
                // We found a cycle in the graph. It is impossible to derive the order of letters.
                return false;
            }
            ancestors.add(root);
            for(char child : graph.get(root)) {
                if(!visited.contains(child)) {
                    if(!DFS(child, graph, visited, ancestors, sb)) {
                        return false;
                    }
                }
            }
            ancestors.remove(root);
            visited.add(root);
            // We have visited all the descendants, so we can output the current node now.
            sb.insert(0, root);
            return true;
        }
    

Log in to reply
 

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