Topological Sort Solution in BFS and DFS by using HashMap<Character, List<Character>> to build graph.


  • 0
    L

    I think this problem is same as the Course Schedule
    https://discuss.leetcode.com/topic/95602/5ms-dfs-beat-98-and-9ms-bfs-in-java
    Besides, we need to output the topological sorted node.
    and I use HashMap<Character,List<Character>> to build graph by comparing the 2 neighbor strings in dictionary to get the edge of graph.
    eg. if "abc" and "abd" exit in dictionary, we could get an edge "c -> d".
    And use HashSet to record the all letters shown in dictionary.

    DFS:

    public class Solution {
        private String res;
    
        public String alienOrder(String[] words) {
            Map<Integer, List<Integer>> graph = makeGraph(words);
    
            boolean[] visited = new boolean[26];
            boolean[] finished = new boolean[26];
            res = new String();
    
            for(Integer s : graph.keySet()) {
                if(!helper(graph, s, visited, finished)) {
                    return new String();
                }
            }
    
            return res;
        }
    
        public Map<Integer, List<Integer>> makeGraph(String[] words) {
            Map<Integer, List<Integer>> graph = new HashMap<>();
            Set<Character> set = new HashSet<>();
            //get all chars show in these dictionary
            for(String word : words) {
                for(char c : word.toCharArray()) {
                    set.add(c);
                }
            }
    
            //initial the adjacent list
            for(Character c : set) {
                graph.put(c - 'a', new ArrayList<Integer>());
            }
    
            //construct the adjacent list
            for(int i = 0; i < words.length - 1; i++) {
                int[] edge = getEdge(words[i], words[i + 1]);
                if(edge != null) {
                    if(!graph.get(edge[0]).contains(edge[1])) {
                        graph.get(edge[0]).add(edge[1]);
                    }
                }
            }
    
            return graph;
        }
    
        public int[] getEdge(String s1, String s2) {
            int[] edge = new int[2];
            int i = 0, j = 0;
            while(i < s1.length() && j < s2.length()) {
                if(s1.charAt(i) != s2.charAt(j)) break;
                i++; j++;
            }
    
            if(i == s1.length() || j == s2.length()) {
                edge = null;
            } else {
                edge[0] = s1.charAt(i) - 'a';
                edge[1] = s2.charAt(j) - 'a';
            }
    
            return edge;
        }
    
        public boolean helper(Map<Integer, List<Integer>> graph, int s, boolean[] visited, boolean[] finished) {
            if(finished[s]) {
                return true;
            } else if(visited[s]) {
                return false;
            } else {
                visited[s] = true;
            }
    
            for(Integer adj : graph.get(s)) {
                if(!helper(graph, adj, visited, finished)) {
                    return false;
                }
            }
    
            visited[s] = false;
            finished[s] = true;
            res = (char)(s + 'a') + res;
            return true;
        }
    
    }
    

    BFS:

    public class Solution {
        public String alienOrder(String[] words) {
            Set<Character> all = new HashSet<>();
            for(String word : words) {
                for(char c : word.toCharArray()) {
                    all.add(c);
                }
            }
    
            Map<Character,Integer> indegree = new HashMap<>();
            Map<Character, List<Character>> graph = new HashMap<>();
            int count = 0;
            for(Character s : all) {
                graph.put(s, new ArrayList<>());
                indegree.put(s, 0);
            }
    
            for(int k = 0; k < words.length - 1; k++) {
                int i = 0, j = 0;
                String s1 = words[k], s2 = words[k + 1];
                while(i < s1.length() && j < s2.length()) {
                    if(s1.charAt(i) != s2.charAt(j)) break;
                    i++; j++;
                }
                if(i == s1.length() || j == s2.length()) {
                    continue;
                } else {
                    char c1 = s1.charAt(i), c2 = s2.charAt(j);
                    graph.get(c1).add(c2);
                    indegree.put(c2, indegree.get(c2) + 1);
                    count++;
                }
            }
    
            Queue<Character> q = new LinkedList<>();
            for(Character s : all) {
                if(indegree.get(s) == 0) {
                    q.offer(s);
                }
            }
    
            StringBuffer res = new StringBuffer();
            while(!q.isEmpty()) {
                Character s = q.poll();
                res.append(s);
    
                for(Character adj : graph.get(s)) {
                    indegree.put(adj, indegree.get(adj) - 1);
                    count--;
                    if(indegree.get(adj) == 0) {
                        q.offer(adj);
                    }
                }
            }
    
            return count == 0 ? res.toString() : "";
        }
    }
    

Log in to reply
 

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