> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/topological-sort/269-alien-dictionary.md).

# 269 Alien Dictionary

## 269. [Alien Dictionary](https://leetcode.com/problems/alien-dictionary/description/)

## 1. Question

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`""`.

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

## 2. Implementation

**(1) BFS**

```java
class Solution {
    public String alienOrder(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }

        Map<Character, Integer> inDegree = new HashMap<>();
        Map<Character, Set<Character>> adjList = new HashMap<>();


        for (String word : words) {
            for (char c : word.toCharArray()) {
                inDegree.put(c, 0);
            }
        }

        for (int i = 0; i < words.length - 1; i++) {
            String curWord = words[i];
            String nextWord = words[i + 1];

            for (int j = 0; j < Math.min(curWord.length(), nextWord.length()); j++) {
                char c1 = curWord.charAt(j);
                char c2 = nextWord.charAt(j);

                // We can only know the lexicographical order from the first two different words
                if (c1 != c2) {
                    Set<Character> set = adjList.getOrDefault(c1, new HashSet<>());

                    if (!set.contains(c2)) {
                        set.add(c2);
                        adjList.put(c1, set);
                        inDegree.put(c2, inDegree.get(c2) + 1);
                    }
                    break;
                }
                // This is not lexicographically order
                else if (j + 1 < curWord.length() && j + 1 == nextWord.length()) {
                    return "";
                }
            }
        }

        Queue<Character> queue = new LinkedList<>();
            for (char key: inDegree.keySet()) {
                if (inDegree.get(key) == 0) {
                    queue.add(key);
                }
            }


        StringBuilder res = new StringBuilder();

        while (!queue.isEmpty()) {
            char curC = queue.remove();
            res.append(curC);

            if (adjList.containsKey(curC)) {
                for (char nextC : adjList.get(curC)) {
                    inDegree.put(nextC, inDegree.get(nextC) - 1);

                    if (inDegree.get(nextC) == 0) {
                        queue.add(nextC);
                    }
                }
            }
        }
        return res.length() == inDegree.size() ? res.toString() : "";
    }
}
```

## 3. Time & Space Complexity

BFS:时间复杂度O(n \* L), n为word的个数，L为每个word的平均长度， 空间复杂度O(k), k为不同的character个数