Leetcode 269. Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:
Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

The correct order is: "wertf".

Example 2:
Given the following words in dictionary,

[
  "z",
  "x"
]

The correct order is: "zx".

Example 3:
Given the following words in dictionary,

[
  "z",
  "x",
  "z"
]

The order is invalid, so return "".

首先根据已知条件建立一个图， 用adjacent list 来表示。

然后 使用 dfs 和一个stack 来 拓扑排序。如果存在 loop的话就返回 false。visited 是 true，则返回 true，继续搜索。

 public String alienOrder(String[] words) {
        Map<Character, List<Character>> graph = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words[i].length(); j++) {
                char c = words[i].charAt(j);
                graph.putIfAbsent(c, new ArrayList<Character>());
            }
            if (i > 0) check(words[i - 1], words[i], graph);
        }
        Stack<Character> stack = new Stack<>();
        boolean[] visited = new boolean[26];
        boolean[] isLoop = new boolean[26];
        for (char c : graph.keySet()) {
            if (!dfs(graph, c, visited, isLoop, stack)) return "";
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) sb.append(stack.pop());
        return sb.toString();
    }
    
    private void check(String word1, String word2, Map<Character, List<Character>> map) {
        int i = 0;
        while (i < word1.length() && i < word2.length() && word1.charAt(i) == word2.charAt(i)) i++;
        if (i < word1.length() && i < word2.length()) map.get(word1.charAt(i)).add(word2.charAt(i));
    }
    
    private boolean dfs(Map<Character, List<Character>> graph, char c, boolean[] visited, boolean[] isLoop, Stack<Character> stack) {
        int i = c - 'a';
        if (visited[i]) return true;
        if (isLoop[i]) return false;
        isLoop[i] = true;
        for (char next : graph.get(c)) {
            if (!dfs(graph, next, visited, isLoop, stack))
                return false;
        }
        visited[i] = true;
        stack.push(c);
        return true;
    }

第二种方法是用 boolean matrix 来表示， 

并用 0 表示 没有访问过

用 1 表示 没有正在访问

用 2 表示 访问过

private final int N = 26;
    public String alienOrder(String[] words) {
        boolean[][] adj = new boolean[N][N];
        int[] visited = new int[N];
        buildGraph(words, adj, visited);
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            if(visited[i] == 0) {                 // unvisited
                if(!dfs(adj, visited, sb, i)) return "";
            }
        }
        return sb.reverse().toString();
    }

    public boolean dfs(boolean[][] adj, int[] visited, StringBuilder sb, int i) {
        visited[i] = 1;                            // 1 = visiting
        for(int j = 0; j < N; j++) {
            if(adj[i][j]) {                        // connected
                if(visited[j] == 1) return false;  // 1 => 1, cycle
                if(visited[j] == 0) {              // 0 = unvisited
                    if(!dfs(adj, visited, sb, j)) return false;
                }
            }
        }
        visited[i] = 2;                           // 2 = visited
        sb.append((char) (i + 'a'));
        return true;
    }

    public void buildGraph(String[] words, boolean[][] adj, int[] visited) {
        Arrays.fill(visited, -1);                 // -1 = not even existed
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) visited[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++) {
                    char c1 = w1.charAt(j), c2 = w2.charAt(j);
                    if (c1 != c2) {
                        adj[c1 - 'a'][c2 - 'a'] = true;
                        break;
                    }
                }
            }
        }
    }

public String alienOrder(String[] words) {
        Map<Character, List<Character>> graph = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < words[i].length(); j++) {
                char c = words[i].charAt(j);
                graph.putIfAbsent(c, new ArrayList<Character>());
            }
            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++) {
                    char c1 = w1.charAt(j), c2 = w2.charAt(j);
                    if (c1 != c2) {
                        graph.get(c1).add(c2);
                        break;
                    } 
                }
            }
        }
        Stack<Character> stack = new Stack<>();
        int[] visited = new int[26];
        for (char c : graph.keySet()) {
            if (!dfs(graph, c, visited, stack)) return "";
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) sb.append(stack.pop());
        return sb.toString();
    }
    // unvisited = 0
    // visiting = 1
    // visited = 2
    private boolean dfs(Map<Character, List<Character>> graph, char c, int[] visited, Stack<Character> stack) {
        int i = c - 'a';
        if (visited[i] == 2) return true;
        if (visited[i] == 1) return false;
        visited[i] = 1;
        for (char next : graph.get(c)) {
            if (!dfs(graph, next, visited, stack))
                return false;
        }
        visited[i] = 2;
        stack.push(c);
        return true;
    }