Java 7ms, two fast methods, DFS and BFS topological sorting


  • 0

    DFS is faster since it only uses one HashMap.
    DFS topological sort + cycle detection, and scan two adjacent string to get precedence order:

        private StringBuilder sb = new StringBuilder();
        private HashMap<Character, HashSet<Character>> followers = new HashMap<>();
        private boolean dfs(char c, HashSet<Character> onpath, HashSet<Character> visited) {
            onpath.add(c);
            HashSet<Character> set = followers.get(c);
            for (char d : set) {
                if (onpath.contains(d)) return false;
                if (!visited.contains(d)) {
                    if (!dfs(d, onpath, visited)) return false;
                }
            }
            sb.append(c);
            onpath.remove(c);
            visited.add(c);
            return true;
        }
        public String alienOrder(String[] words) {
            if (words.length == 1) return words[0];
            for (String s : words) {
                char[] chs = s.toCharArray();
                for (char c : chs) {
                    followers.put(c, new HashSet<>());
                }
            }
            for (int i = 0; i < words.length-1; i++) {
                char[] s1 = words[i].toCharArray(), s2 = words[i+1].toCharArray();
                int len = Math.min(s1.length, s2.length);
                for (int j = 0; j < len; j++) {
                    if (s1[j] != s2[j]) {
                        followers.get(s1[j]).add(s2[j]);
                        break;
                    }
                }
            }
            HashSet<Character> onpath = new HashSet<>(), visited = new HashSet<>();
            for (char c : followers.keySet()) {
                if (!visited.contains(c)) {
                    if (!dfs(c, onpath, visited)) return "";
                }
            }
            return sb.reverse().toString();
        }
    

    BFS using two HashMap and using MSD recursion to get precedence order:

        private HashMap<Character, HashSet<Character>> followees = new HashMap<>();
        private HashMap<Character, Integer> followers = new HashMap<>();
        private void findDiff(String[] words, int start, int end, int pos) {
            while (start < end && pos >= words[start].length()) start++;
            if (start == end) return;
            char a = words[start].charAt(pos);
            for (int i = start+1; i <= end; i++) {
                char b = words[i].charAt(pos);
                if (b != a) {
                    if (followees.get(b).add(a)) {
                        followers.put(a, followers.get(a)+1);
                    }
                    findDiff(words, start, i-1, pos+1);
                    a = b;
                    start = i;
                }
            }
            findDiff(words, start, end, pos+1);
        }
        public String alienOrder(String[] words) {
            for (String s : words) {
                char[] chs = s.toCharArray();
                for (char c : chs) {
                    followees.put(c, new HashSet<>());
                    followers.put(c, 0);
                }
            }
            findDiff(words, 0, words.length-1, 0);
            LinkedList<Character> queue = new LinkedList<>();
            StringBuilder sb = new StringBuilder();
            int count = followers.size();
            for (char c : followers.keySet()) {
                if (followers.get(c) == 0) {
                    queue.add(c);
                    sb.append(c);
                    count--;
                }
            }
            while (!queue.isEmpty() && count > 0) {
                char c = queue.poll();
                HashSet<Character> set = followees.get(c);
                for (char d : set) {
                    int i = followers.get(d)-1;
                    if (i == 0) {
                        queue.add(d);
                        sb.append(d);
                        count--;
                    } else {
                        followers.put(d, i);
                    }
                }
            }
            return count == 0 ? sb.reverse().toString() : "";
        }
    

Log in to reply
 

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