Java BFS Adjacency Matrix Solution


  • 0
    I
        public String alienOrder(String[] words) {
            if (words.length == 0) return "";
    
            int[][] graph = new int[26][26];
            int[] degree = new int[26];
            StringBuilder sb = new StringBuilder();
    
            for (int i=0;i<words.length;i++) {
                for (int j=0;j<words[i].length();j++) {
                    degree[words[i].charAt(j)-'a']=1;
                }
            }
    
            for (int i=1;i<words.length;i++) {
                int j;
                for (j=0;j<Math.min(words[i-1].length(), words[i].length());j++) {
                    char ch1 = words[i-1].charAt(j), ch2= words[i].charAt(j);
                    if (ch1!=ch2) {
                        if (graph[ch1-'a'][ch2-'a']==0) {
                            graph[ch1 - 'a'][ch2 - 'a'] = 1;
                            degree[ch2 - 'a']++;
                        }
                        break;
                    }
                }
                if (j == words[i].length() && j<words[i-1].length()) return "";
            }
    
            Queue<Integer> queue = new LinkedList<>();
            for (int i=0;i<26;i++) {
                if (degree[i]==1) queue.offer(i);
            }
    
            while (!queue.isEmpty()) {
                Integer cur = queue.poll();
                sb.append((char)('a'+cur));
    
                for (int i=0;i<26;i++) {
                    if (graph[cur][i]==1 && degree[i]>=1) {
                        degree[i]--;
                        if (degree[i]==1) queue.offer(i);
                    }
                }
            }
    
            for (int i=0;i<26;i++) {
                if (degree[i]>1) return "";
            }
    
            return sb.toString();
        }
    

Log in to reply
 

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