> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/alien-dictionary.md).

# 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.

1. You may assume all letters are in lowercase.
2. The dictionary is invalid, if a is prefix of b and b is appear before a.
3. If the order is invalid, return an empty string.
4. There may be multiple valid order of letters, return the smallest in normal lexicographical order

#### Example

**Example 1:**

```
Input：["wrt","wrf","er","ett","rftt"]
Output："wertf"
Explanation：
from "wrt"and"wrf" ,we can get 't'<'f'
from "wrt"and"er" ,we can get 'w'<'e'
from "er"and"ett" ,we can get 'r'<'t'
from "ett"and"rftt" ,we can get 'e'<'r'
So return "wertf"

```

**Example 2:**

```
Input：["z","x"]
Output："zx"
Explanation：
from "z" and "x"，we can get 'z' < 'x'
So return "zx"
```

```java
public class Solution {
    public String alienOrder(String[] words) {
        ArrayList<Integer>[] graph = new ArrayList[26];
        // Creating graph
        for (int i = 0; i < words.length; i++) {
            // Only creating those nodes which exists
            for (int j = 0; j < words[i].length(); j++)
                if (graph[words[i].charAt(j) - 'a'] == null)
                    graph[words[i].charAt(j) - 'a'] = new ArrayList<>();

            if (i != 0) {
                int j = 0;
                while (j < Math.min(words[i].length(), words[i - 1].length())
                        && words[i].charAt(j) == words[i - 1].charAt(j))
                    j++;
                // Direction graph from smaller to bigger char(alien lexically)
                if (j != Math.min(words[i].length(), words[i - 1].length()))
                    graph[words[i - 1].charAt(j) - 'a'].add(words[i].charAt(j) - 'a');
            }
        }
        // Creating indegree array
        int[] indegree = new int[26];
        Arrays.fill(indegree, -1);
        int count = 0;
        // Indegree =-1 implies that nodes does not exists
        for (int i = 0; i < 26; i++) {
            if (graph[i] != null) {
                indegree[i] = 0;
                count++;
            }
        }
        for (int i = 0; i < 26; i++) {
            if (graph[i] != null) {
                for (int x : graph[i])
                    indegree[x]++;
            }
        }
        // Topological Sort
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for (int i = 0; i < 26; i++)
            if (indegree[i] == 0)
                q.add(i);
        StringBuilder ans = new StringBuilder();
        while (q.size() != 0) {
            char c = (char) (q.poll() + 'a');
            ans.append(c);
            for (int x : graph[c - 'a']) {
                indegree[x]--;
                if (indegree[x] == 0)
                    q.add(x);
            }
        }
        // If a cycle exists then return empty string
        return ans.length() == count ? ans.toString() : "";
    }
}
```