https://leetcode.com/problems/alien-dictionary/

alien-dictionary-v1.java

class Solution {
    public String alienOrder(String[] words) {
        boolean[][] adjacent = new boolean[26][26];
        // -1: no exist, 0: exist, 1: visiting, 2: visited
        int[] visited = new int[26];
        int[] indegree = new int[26];
        
        Arrays.fill(visited, -1);
        
        if (!buildGraph(adjacent, visited, words)) {
            return "";
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 25; i >= 0; i--) {
            if (visited[i] == 0) {
                if (!search(adjacent, visited, (char)('a' + i), sb)) {
                    return "";
                }
            }
        }
        
        return sb.reverse().toString();
    }
    
    public boolean search(boolean[][] adjacent, int[] visited, char c, StringBuilder sb) {
        if (visited[c - 'a'] == 1) { //cycle
            return false;
        }
        if (visited[c - 'a'] == 2) { //finished
            return true;
        }
        visited[c - 'a'] = 1;
        for (int i = 0; i < 26; i++) {
            if (adjacent[c - 'a'][i]) {
                if (!search(adjacent, visited, (char)('a' + i), sb)) {
                    return false;
                }   
            }
        }
        visited[c - 'a'] = 2;
        sb.append(c);
        return true;
    }
    
    
    public boolean buildGraph(boolean[][] adjacent, int[] visited, String[] words) {
        
        for (int i = 0; i < words.length; i++) {
            for (int k = 0; k < words[i].length(); k++) {
                visited[words[i].charAt(k) - 'a'] = 0; // mark as exist
            }
            if (i == 0) {
                continue;
            }
            String word1 = words[i - 1];
            String word2 = words[i];
            int len = Math.min(word1.length(),word2.length());
            boolean found = false; // found diff
            for (int k = 0; k < len; k++) {
                if (word1.charAt(k) != word2.charAt(k)) {
                    adjacent[word1.charAt(k) - 'a'][word2.charAt(k) - 'a'] = true;
                    found = true;
                    break;
                }
            }
            if (!found && word1.length() > word2.length()) {
                return false;
            }
        }
        return true;
    } 
}

alien-dictionary-v2.java

class Solution {
    public String alienOrder(String[] words) {
        boolean[][] adjacent = new boolean[26][26];
        boolean[] exist = new boolean[26];
        int[] indegree = new int[26];
        
        if (!buildGraph(adjacent, exist, indegree, words)) {
            return "";
        }
        
        Queue<Character> queue = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < 26; i++) {
            if (exist[i] && indegree[i] == 0) {
                //System.out.println("init: " + i);
                queue.offer((char)('a' + i));
            }
            if (exist[i]) {
                count += 1;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        while(!queue.isEmpty()) {
            char curr = queue.poll();
            for (int i = 0; i < 26; i++) {
                if (adjacent[curr - 'a'][i] && exist[i]) {
                    if (--indegree[i] == 0) {
                        queue.offer((char)('a' + i));
                    }
                }
            }
            sb.append(curr);
            count -= 1;
        }
        //System.out.println("out: " + sb.toString());
        return count == 0 ? sb.toString() : "";
    }
    
    public boolean buildGraph(boolean[][] adjacent, boolean[] exist, int[] indegree, String[] words) {
        
        for (int i = 0; i < words.length; i++) {
            for (int k = 0; k < words[i].length(); k++) {
                exist[words[i].charAt(k) - 'a'] = true; // mark as exist
            }
            if (i == 0) {
                continue;
            }
            String word1 = words[i - 1];
            String word2 = words[i];
            int len = Math.min(word1.length(),word2.length());
            boolean found = false;
            for (int k = 0; k < len; k++) {
                if (word1.charAt(k) != word2.charAt(k)) {
                    if (!adjacent[word1.charAt(k) - 'a'][word2.charAt(k) - 'a']) {
                        adjacent[word1.charAt(k) - 'a'][word2.charAt(k) - 'a'] = true;
                        indegree[word2.charAt(k) - 'a'] += 1;
                    } 
                    found = true;
                    break;
                }
            }
            if (!found && word1.length() > word2.length()) {
                return false;
            }
        }
        return true;
    }   
}