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
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;
}
};
Last updated
Was this helpful?