# Alien Dictionary

`Graph`, `Topological Sorting`

**Hard**

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:**

```
Input:

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


Output: "wertf"
```

**Example 2:**

```
Input:

[
  "z",
  "x"
]


Output: "zx"
```

**Example 3:**

```
Input:

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


Output:""
Explanation: The order is invalid, so return "".
```

**Note:**

1. You may assume all letters are in lowercase.
2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
3. If the order is invalid, return an empty string.
4. There may be multiple valid order of letters, return any one of them is fine.

## Analysis & Solution

**问题转化**：alien单词字母表的先后顺序转化为依赖关系，那么这个字母表顺序就可以通过拓扑排序来得到。

### Topological Sorting - BFS

通过input words建立邻接表，记录In-degree的数目，从in-degree为0的节点（字母）开始，放入Queue中，进行BFS。

接下来的就是用Kahn's aglorithm来做topological sort。

**注意的要点：**

1. 如何将alien dictionary转化为邻接表
   1. 循环words\[]，words\[i], words\[i + 1]从头进行字符比较，如果出现不一样的字符 ch1 != ch2，说明存在lexicographical的关系（ch1 在 ch2之前），就可以记录ch2在ch1的邻接表中，并更新ch2的indegree加1。 因为从topological的角度，就是ch1依赖ch2，所以是ch2的indegree + 1。
2. 如何初始化indegree的计数
   1. 有个tricky的地方在于如果用int indegree\[]来记录，因为数组初始化默认都为0，所以不能仅仅凭借indegree\[i - 'a']判断是否入度降为0，而需要额外辅助的set，记录在alien dictionary中出现过的字符。
   2. 或者用一个HashMap\<Character, Integer> 进行记录，这样既可以计数indegree，也满足只记录alien dict出现的字符
3. 何时更新indegree的计数
   1. 每次在queue中poll()之后，相当于要对这个ch对应的所有依赖的字符更新indegree，也就是在adjacency list邻接表中遍历对应的字符，再更新indegree的记录-1.
4. 如何判断是否存在topological sorting
   1. 如果存在topological sorting，那么最后result的长度应该等于alien dictionary的key的个数
   2. 或者检测indegree hashmap中的每个字符indegree计数，如果有一个不为0，则说明不满足

**代码：**

```java
class Solution {
    public String alienOrder(String[] words) {
        String result = "";
        if (words == null || words.length == 0) {
            return result;
        }
        HashMap<Character, HashSet<Character>> adj = new HashMap<>();
        HashMap<Character, Integer> indegree = new HashMap<>();

        // Initiate indegree for characters in the alien dict
        for (String word: words) {
            for (char c: word.toCharArray()) {
                indegree.put(c, 0);
            }
        }

        // Build graph with adjacency list; update indegree
        for (int i = 0; i < words.length - 1; i++) {
            int j = 0;
            while (j < words[i].length() && j < words[i + 1].length()) {
                char a = words[i].charAt(j);
                char b = words[i + 1].charAt(j);
                if (a != b) {
                    HashSet<Character> set = new HashSet<>();
                    if (adj.containsKey(a)) {
                        set = adj.get(a);
                    }
                    if (!set.contains(b)) {
                        set.add(b);
                        adj.put(a, set);
                        indegree.put(b, indegree.get(b) + 1);
                    }
                    break;
                }
                j++;
            }
        }

        // Initiate queue for topological sorting
        Queue<Character> q = new LinkedList<>();
        for (Character c: indegree.keySet()) {
            if (indegree.get(c) == 0) {
                q.offer(c);
            }
        }

        // Topological Sorting
        while (!q.isEmpty()) {
            char ch = q.poll();
            result += ch;
            if (adj.containsKey(ch)) {
                for (char c : adj.get(ch)) {
                    indegree.put(c, indegree.get(c) - 1);
                    if (indegree.get(c) == 0) {
                        q.offer(c);
                    }
                }
            }
        }

        // No valid topological sorting
        if (result.length() != indegree.size()) {
            return "";
        }

        return result;
    }

}
```

### Topological Sorting - DFS

by [@yavinci:](https://leetcode.com/problems/alien-dictionary/discuss/70115/3ms-Clean-Java-Solution-%28DFS%29)

The key to this problem:

> **A topological ordering is possible if and only if the graph has no directed cycles**

Let's build a graph and perform a DFS. The following states made things easier.

1. `visited[i] = -1`. Not even exist.
2. `visited[i] = 0`. Exist. Non-visited.
3. `visited[i] = 1`. Visiting.
4. `visited[i] = 2`. Visited.

```java
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;
                }
            }
        }
    }
}
```

#### Another DFS - More Modularized

```java
class Solution {
    public String alienOrder(String[] dict) {
        // corner case
        if (dict == null || dict.length == 0) {
            return new String();
        }

        if (dict.length == 1) {
            return dict[0];
        }

        Map<Character, Set<Character>> graph = initialGraph(dict);

        return topoOrder(graph);
    }

    private Map<Character, Set<Character>> initialGraph(String[] dict) {
        Map<Character, Set<Character>> graph = new HashMap<>();

        // each adjacent pairs
        for (int i = 1; i < dict.length; i++) {
            String one = dict[i - 1];
            String two = dict[i];
            addEdge(one, two, graph);
        }

        return graph;
    }

    private void addEdge(String one, String two, 
                            Map<Character, Set<Character>> graph) {
        for (int i = 0; i < one.length(); i++) {
            graph.putIfAbsent(one.charAt(i), new HashSet<Character>());
        }

        for (int i = 0; i < two.length(); i++) {
            graph.putIfAbsent(two.charAt(i), new HashSet<Character>());
        }

        for (int i = 0; i < one.length() && i < two.length(); i++) {
            if (one.charAt(i) != two.charAt(i)) {
                graph.get(one.charAt(i)).add(two.charAt(i));
                return;
            }
        }

    }

    private String topoOrder(Map<Character, Set<Character>> graph) {
        StringBuilder sb = new StringBuilder();
        // recording visit status, -1 is visiting , 1 is visited
        Map<Character, Integer> visited = new HashMap<>();

        for (Character v : graph.keySet()) {
            visited.put(v, 0);
        }
        for (Character v : graph.keySet()) {
            if (traverse(graph, v, visited, sb)) {
                return new String();
            }
        }

        return sb.reverse().toString();
    }

    // traverse graph from v, return true if there is cycle.
    // also record the order of visited order
    private boolean traverse(Map<Character, Set<Character>> graph, Character v,
                    Map<Character, Integer> visited, StringBuilder sb) {
        // base case
        if (visited.get(v) == -1) {
            return true;
        }

        if (visited.get(v) == 1) {
            return false;
        }

        // mark visiting
        visited.put(v, -1);
        for (Character nei : graph.get(v)) {
            if (traverse(graph, nei, visited, sb)) {
                return true;
            }
        }

        visited.put(v, 1);
        sb.append(v);
        return false;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/graph_search/alien-dictionary.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.