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

# LeetCode 269. Alien Dictionary

Topological Sort

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings `words` from the alien language's dictionary, where the strings in `words` are **sorted lexicographically** by the rules of this new language.

Return *a string of the unique letters in the new alien language sorted in **lexicographically increasing order** by the new language's rules. If there is no solution, return* `""`*. If there are multiple solutions, return **any of them***.

A string `s` is **lexicographically smaller** than a string `t` if at the first letter where they differ, the letter in `s` comes before the letter in `t` in the alien language. If the first `min(s.length, t.length)` letters are the same, then `s` is smaller if and only if `s.length < t.length`.

**Example 1:**

```
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
```

**Example 2:**

```
Input: words = ["z","x"]
Output: "zx"
```

**Example 3:**

```
Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return "".
```

**Constraints:**

* `1 <= words.length <= 100`
* `1 <= words[i].length <= 100`
* `words[i]` consists of only lowercase English letters.

## Solution

[English Version in Youtube](https://youtu.be/OsjodfsorBs)

[中文版解答Youtube Link](https://youtu.be/5slT8ZfVKrQ)

[中文版解答Bilibili Link](https://www.bilibili.com/video/BV1NU4y1h7Ww/)

```
class Solution {
    bool dfs(char ch,
             unordered_map<char, vector<char>>& graph,
             unordered_map<char, int>& colors,
             string& order) {
        colors[ch] = 1;
        for (char neighbor : graph[ch]) {
            if (colors[neighbor] == 1) {
                return true;
            }
            if (colors[neighbor] == 0) {
                bool has_circle = dfs(neighbor, graph, colors, order);
                if (has_circle) {
                    return true;
                }
            }
        }
        order.push_back(ch);
        colors[ch] = 2;
        return false;
    }
    
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, vector<char>> graph;
        for (int i = 1; i < words.size(); i++) {
            int len = min(words[i-1].size(), words[i].size());
            for (int j = 0; j < len; j++) {
                if (words[i-1][j] != words[i][j]) {
                    graph[words[i-1][j]].push_back(words[i][j]);
                    break;
                }
                if (j == len - 1 && words[i].size() < words[i-1].size()) {
                    return "";
                }
            }
        }
        
        unordered_map<char, int> colors;
        for (const string& word : words) {
            for (char ch : word) {
                colors[ch] = 0;
            }
        }
        
        string res;
        for (const auto& [ch, color] : colors) {
            if (color == 0) {
                if (dfs(ch, graph, colors, res)) {
                    return "";
                }
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
```