Java BFS TOPO


  • 0
    V
    public class Solution {
        private static final int N = 26;
        public String alienOrder(String[] words) {
            Map<Integer, Set<Integer>> graph = new HashMap<>();
            
            int[] deps = new int[N];
            boolean[] exists = new boolean[N];
            int numValid = 0;
            for(int i = 0; i < words.length; i++) {
                String w1 = words[i];
                for (char c : w1.toCharArray()) {
                    if (!graph.containsKey(c - 'a')) {
                        numValid++;
                        exists[c - 'a'] = true;
                        graph.put(c - 'a', new HashSet<>());
                    }
                }
                
                for (int j = i + 1; j < words.length; j++) {
                    String w2 = words[j];
                    
                    int s = 0, t = 0;
                    while( s < w1.length() && t < w2.length() && w1.charAt(s) == w2.charAt(t)) {
                        s++; t++;
                    }
                    
                    if (s < w1.length() && t < w2.length()) {
                        if (!graph.get(w1.charAt(s) - 'a').contains(w2.charAt(t) - 'a')) {
                            graph.get(w1.charAt(s) - 'a').add(w2.charAt(t) - 'a');
                            deps[w2.charAt(t) - 'a']++;
                        }
                    }
                }
            }
            
            List<Integer> active = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                if (deps[i] == 0 && exists[i]) active.add(i);
            }
            
            List<Integer> topo = new ArrayList<>();
            for (int i = 0; i < numValid && (active.size() > 0); i++) {
                int u = active.get(0);
                for(int v : graph.get(u)) {
                    if (--deps[v] == 0) active.add(v);
                }
                topo.add(u);
                active.remove(0);
            }
            
            StringBuilder sb = new StringBuilder();
            if (topo.size() == numValid) {
                for (int i = 0; i < topo.size(); i++) {
                    sb.append((char)('a' + topo.get(i)));
                }
            }
            
            return sb.toString();
        }
    }
    

Log in to reply
 

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