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

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.

``````t->f
w->e
r->t
e->r
``````

``````class Solution {
public:
string alienOrder(vector<string>& words) {
set<pair<char, char>> st;
unordered_set<char> ch;
vector<int> in(256);
queue<char> q;
string res;
for (auto a : words) ch.insert(a.begin(), a.end());
for (int i = 0; i < (int)words.size() - 1; ++i) {
int mn = min(words[i].size(), words[i + 1].size()), j = 0;
for (; j < mn; ++j) {
if (words[i][j] != words[i + 1][j]) {
st.insert(make_pair(words[i][j], words[i + 1][j]));
break;
}
}
if (j == mn && words[i].size() > words[i + 1].size()) return "";
}
for (auto a : st) ++in[a.second];
for (auto a : ch) {
if (in[a] == 0) {
q.push(a);
res += a;
}
}
while (!q.empty()) {
char c = q.front(); q.pop();
for (auto a : st) {
if (a.first == c) {
--in[a.second];
if (in[a.second] == 0) {
q.push(a.second);
res += a.second;
}
}
}
}
return res.size() == ch.size() ? res : "";
}
};
``````

``````class Solution {
public:
string alienOrder(vector<string>& words) {
vector<vector<bool>> g(26, vector<bool>(26));
vector<bool> visited(26);
string res;
for (string word : words) {
for (char c : word) {
g[c - 'a'][c - 'a'] = true;
}
}
for (int i = 0; i < (int)words.size() - 1; ++i) {
int mn = min(words[i].size(), words[i + 1].size()), j = 0;
for (; j < mn; ++j) {
if (words[i][j] != words[i + 1][j]) {
g[words[i][j] - 'a'][words[i + 1][j] - 'a'] = true;
break;
}
}
if (j == mn && words[i].size() > words[i + 1].size()) return "";
}
for (int i = 0; i < 26; ++i) {
if (!dfs(g, i, visited, res)) return "";
}
return res;
}
bool dfs(vector<vector<bool>>& g, int idx, vector<bool>& visited, string& res) {
if (!g[idx][idx]) return true;
visited[idx] = true;
for (int i = 0; i < 26; ++i) {
if (i == idx || !g[i][idx]) continue;
if (visited[i]) return false;
if (!dfs(g, i, visited, res)) return false;
}
visited[idx] = false;
g[idx][idx] = false;
res += 'a' + idx;
return true;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/269

Minimum Height Trees

Course Schedule II

Course Schedule

https://leetcode.com/problems/alien-dictionary/

https://leetcode.com/problems/alien-dictionary/discuss/70169/my-concise-java-solution-based-on-topological-sorting

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation