# 269 Alien Dictionary

input: list of words，照外星語言字典的字母順序排列。
output: 找出外星語言的字母順序

e.g.

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

output: wertf

Concept:

直覺想法是建一個graph，只要找到一條path 可以走過graph裡的每個node，該path就是字母順序。

Implementation:
實作上，graph會以一個26*26的 adjacency matrix表示字母兩兩之間的相鄰關係。

int[] visited 長度為26（個字母），輔助dfs。

1. boolean[][] adj
   每次讀進input的兩個字，

   wrt
   wrf
   

   則adj[t][f]=True（若上下字母相同不用管相鄰關係）

   | | e | f | r | t | w | | :--- | :--- | :--- | :--- | :--- | :--- | | e | | | T | | | | f | | | | | | | r | | | | T | | | t | | T | | | | | w | T | | | | |

2. int[] visited
   -1 = not even existed
   0 = not visited
   1 = is visiting
   2 = visited

3. main()
   先呼叫buildGraph()，把graph建好。
   宣告一個stringbuilder來存答案。
   建好之後，loop through all alphabet，
   若該visited[alphabet] = 0，表示存在，但還沒被拜訪過，
   則呼叫dfs，以範例來說，會依序append f,t,r,e到sb，
   最後append w，再reverse -> w e r t f

4. dfs()
   先將visited[i]設為1，
   loop through all alphabet，
   如果visited[alphabet]為0，表示存在但尚未拜訪過，
   呼叫dfs()
   跑完全部字母後，設visited[i]為2，表示拜訪過了，
   append i到sb，return true。

5. buildgraph()
   先把visited[]全設為-1，再照上述adj的規則填入true or false，
   唯一需要注意的是，
   若第i個字和第i-1個字不相等，但第i個字是第i-1個字的subsubtring，
   則將visited全設為2，因為這是不合法的排列，應該直接return ""

Code:

public class Solution {
    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];
            if (!w1.equals(w2) && w1.startsWith(w2)) {
                Arrays.fill(visited, 2);
                return;
            }
            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;
                }
            }
        }
    }
}
}