Java BFS Solution


  • 22
    public String alienOrder(String[] words) {
        List<Set<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            adj.add(new HashSet<Integer>());
        }
        int[] degree = new int[26];
        Arrays.fill(degree, -1);
        
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                if (degree[c - 'a'] < 0) {
                    degree[c - 'a'] = 0;
                }
            }
            if (i > 0) {
                String w1 = words[i - 1], w2 = words[i];
                int len = Math.min(w1.length(), w2.length());
                for (int j = 0; j < len; j++) {
                    int c1 = w1.charAt(j) - 'a', c2 = w2.charAt(j) - 'a';
                    if (c1 != c2) {
                        if (!adj.get(c1).contains(c2)) {
                            adj.get(c1).add(c2);
                            degree[c2]++;
                        }
                        break;
                    }
                    if (j == w2.length() - 1 && w1.length() > w2.length()) { // "abcd" -> "ab"
                        return "";
                    }
                }
            }
        }
        
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < degree.length; i++) {
            if (degree[i] == 0) {
                q.add(i);       
            }
        }
        
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            int i = q.poll();
            sb.append((char) ('a'  + i));
            for (int j : adj.get(i)) {
                degree[j]--;
                if (degree[j] == 0) {
                    q.add(j);        
                }
            }
        }
        
        for (int d : degree) {
            if (d > 0) {
                return "";
            }
        }
        
        return sb.toString();
    }

  • 0
    Y

    great code! i like the part about using array as well as building adj list and indegree table at the same time.


  • 0

    @yanggao, thanks, You got it! It looks like you've read the code carefully :)


  • 0
    Y

    The key point for this problem is to build the graph, it is quite easy to understand, thank you for your code.


  • 0
    H

    I wonder why 'break' is in the 'if(!adj.get(c1).contains(c2))' clause. If we have words [ad, ag, bdc, bga, c], we may generate c -> a, which is not true.


  • 0
    I

    Nice and clean!

    One thing I am not clear is: why building graph based on adjacent words is enough? Don't we need to build graph based on all pairs of words?


  • 0
    J

    Should the break in if(!adj.get(c1).contains(c2)) {
    adj.get(c1).add(c2);
    degree[c2]++;
    break;
    }

    outside the }, I thought every time there is w1.charAt(j) != w2.charAt(j), it should break after the operations.


  • 3
    F

    This code cannot pass all the tests.....


  • 1
    A

    @fangcheng626 I ended up fixing this by modifying as such:

    public class Solution {
        private int aLen = 26;                  // len of alphabet
        public String alienOrder(String[] words) {
            // https://discuss.leetcode.com/topic/32900/easiest-java-bfs-solution/2
            // Toposort problem
            // BUILD GRAPH:
            ArrayList<HashSet<Integer>> neighbours = new ArrayList<>(aLen);       // adjacency list of nodes
            int[] degree = new int[aLen];      // degrees incoming
            buildGraph(words, degree, neighbours);
            
            // TOPOLOGICAL SORT:
            // The starting frontier is all characters with inbound edges of 0 since
            // the are earliest in the alien alphabet. Reduce all neighbours'
            // inbound edges by 1 since now we can reach to them next. If any of them
            // turn to 0, then add those to the frontier and repeat. Store the polled
            // values with inbound edges 0 in order that they come out. This is the
            // lexicographical ordering of the alien alphabet.
            StringBuilder sb = new StringBuilder();
            Queue<Integer> q = new LinkedList<Integer>();
            for (int i = 0; i < degree.length; i++) {
                if (degree[i] == 0) q.add(i);
            }
    
            while (!q.isEmpty()) {
                int curr = (int) q.poll();
                sb.append((char) (curr + 'a'));
                for (Integer i : neighbours.get(curr)) {
                    degree[i] = degree[i] - 1;
                    if (degree[i] == 0) q.add(i);
                }
            }
            
            // check if there are any characters to which we could not resolve.
            // if there exists any with deg > 0, then there was not substantial
            // data to decide where this character belonged
            for (int i = 0; i < degree.length; i++) {
                if (degree[i] > 0) return "";
            }
            
            return sb.toString();
    
        }
        
        /* Step 1: build the graph.
        * For each character, count how many inbound edges there are,
        * where an inbound edge is defined s.t. for words w1 and w2,
        * where charAt(w1) != charAt(w2), w1 -> w2. We also keep a 
        * running list of neighbours for each character. */
        public void buildGraph(String[] words, int[] deg, ArrayList<HashSet<Integer>> n) {
            // init the neighbours array
            for (int i = 0; i < aLen; i++) n.add(new HashSet<Integer>());
            for (int i = 0; i < deg.length; i++) {
                deg[i] = -1;                // representing as not in the array
            }
            
            for (int i = 0; i < words.length; i++) {
                // build the indegrees for each character
                String currString = words[i];
                for (int j = 0; j < currString.length(); j++) {
                    int currChar = currString.charAt(j) - 'a';
                    if (deg[currChar] < 0) deg[currChar] = 0;           // set this character as seen if not yet
                }
            }
                
            for (int i = 1; i < words.length; i++) {
                // we want to compare pairs of words at idx words[i] and words[i+1]
                // for every letter in words[i], if we see that charAt(j_i) != charAt(j_i+1),
                // then we know that there is an inbound edge pointing from charAt(j_i) -> charAt(j_i+1),
                // since the char from w_i should come before w_i+1 lexiographically.
                String w1 = words[i-1];
                String w2 = words[i];
                
                if (w1.length() > w2.length()) {
                    // corner case s.t. we might have "wrtkj" come before "wrt",
                   // but this must never be the case
                    if (w1.substring(0, w2.length()).equals(w2)) {
                        Arrays.fill(deg, 5);
                        return;
                    }
                }
                
                for (int k = 0; k < Math.min(w1.length(), w2.length()); k++) {
                    int c1 = w1.charAt(k) - 'a';
                    int c2 = w2.charAt(k) - 'a';
    
                    if (c1 != c2) {
                        // c1 -> c2 must be true
                        if (!n.get(c1).contains(c2)) {
                            // does c1 point to c2 already? 
                            // don't want to double count or produce a cycle
                            n.get(c1).add(c2);
                            deg[c2] = deg[c2] + 1;        // update the inbound for c2
                        }
                        break;                              // insubstantial evidence past this mismatch
    
                    }
                }
            }
        }
    }
    
    

  • 0

    @fangcheng626 Fixed. Thanks!


Log in to reply
 

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