Java solution using BFS - Passed all updated test cases


  • 0
    J
    public class Solution {
        public String alienOrder(String[] words) {
            Set<Integer>[] adMatrix = new HashSet[26];
            int[] indegree = new int[26];
            Arrays.fill(indegree, -1);
            for (int i = 0; i < words.length; i ++) {
                // Set indegree[] with input chars
                for (int j = 0; j < words[i].length(); j ++) {
                    int curChar = words[i].charAt(j) - 'a';
                    if (indegree[curChar] == -1) {
                        indegree[curChar] = 0;
                    }
                }
                if (i != 0) {
                    String first = words[i - 1];
                    String second = words[i];
                    int len = Math.min(first.length(), second.length());
                    for (int ix = 0; ix < len; ix ++) {
                        int src = first.charAt(ix) - 'a';
                        int dst = second.charAt(ix) - 'a';
                        if (src != dst) {
                            if (adMatrix[src] == null) {
                                adMatrix[src] = new HashSet<>();
                            }
                            if (adMatrix[src].add(dst)) {
                                indegree[dst] += 1;
                            }
                            break;
                        }
                        if (ix == len - 1 && first.length() > second.length()) {
                            return "";
                        }
                    }                
                }
            }
            //Do bfs for each src node
            Queue<Integer> myQueue = new LinkedList<>();
            // First, put valid src into myQueue
            for (int i = 0; i < indegree.length; i ++) {
                if (indegree[i] == 0) {
                    myQueue.offer(i);
                }
            }
            StringBuilder resultPath = new StringBuilder();// save path result
            int counter = 0;// check if the order is valid
            for (int i = 0; i < indegree.length; i ++) {
                if (indegree[i] != -1) {
                    counter ++;
                }
            }
            while (!myQueue.isEmpty()) {
                // put the letter into result when we poll it out
                int cur = myQueue.poll();
                resultPath.append((char)(cur + 'a'));
                counter --;
                // use its adjacency matrix to get its next hop information
                if (adMatrix[cur] != null) {
                    for (int nextValue: adMatrix[cur]) {
                        indegree[nextValue] --;
                        if (indegree[nextValue] == 0) {
                            myQueue.offer(nextValue);
                        }
                    }                
                }
            }
            if (counter == 0) {
                return resultPath.toString();
            } else {
                return "";
            }
        }
    }
    

Log in to reply
 

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