Topological Sort - Clean Java Solution


  • 0
    M
    public class Solution {
        private class GNode {
            char c;
            int inD;
            Set<GNode> neib;
            public GNode(char val) {
                c = val;
                neib = new HashSet<>();
                inD = 0;
            }
        }
        public String alienOrder(String[] words) {
            if (words == null || words.length == 0) return "";
            Map<Character, GNode> V = new HashMap<>();
            for (String word : words) {
                for (char c : word.toCharArray()) {
                    if (!V.containsKey(c)) V.put(c, new GNode(c));
                }
            }
            for (int i = 0; i < words.length - 1; ++i) {
                buildGraph(words[i], words[i + 1], V);
            }
            List<GNode> topoList = topoSort(V);
            if (topoList.size() == 0) return "";
            StringBuilder res = new StringBuilder();
            for (GNode node : topoList) res.append(node.c);
            return res.toString();
        }
        private void buildGraph(String a, String b, Map<Character, GNode> V) {
            int i = 0, j = 0;
            while (i < a.length() && j < b.length()) {
                char p = a.charAt(i), q = b.charAt(j);
                if (p != q) {
                    if (!V.get(p).neib.contains(V.get(q))) {
                        V.get(p).neib.add(V.get(q));
              	 		++V.get(q).inD;
                    }
                    break;
                }
                ++i;
                ++j;
            }
        }
        private List<GNode> topoSort(Map<Character, GNode> V) {
            List<GNode> res = new LinkedList<>();
            List<GNode> list = new LinkedList<>();
            for (GNode node : V.values()) {
                if (node.inD == 0) list.add(node);
            }
            if (list.size() == 0) return res;
            res.addAll(list);
            while (list.size() != 0) {
                List<GNode> next = new LinkedList<>();
                for (GNode node : list) {
                    for (GNode neib : node.neib) {
                        if (--neib.inD == 0) next.add(neib);
                    }
                }
                list = next;
                res.addAll(list);
            }
            return res.size() == V.size() ? res : new LinkedList<GNode>();
        }
    }
    

Log in to reply
 

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