1. Description
There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you.
You are given a list of strings words from the alien language’s dictionary. Now it is claimed that the strings in words are sorted lexicographically by the rules of this new language.
If this claim is incorrect, and the given arrangement of string in words cannot correspond to any order of letters, return “”.
Otherwise, 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 are multiple solutions, return any of them.
2. Example
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 “”.
3. Constraints
- 1 <= words.length <= 100
- 1 <= words[i].length <= 100
- words[i] consists of only lowercase English letters.
4. Solutions
Breadth-First Search
N = words.size(), V = indegree.size(), E = next_letters.size()
Time complexity: O(N + V + E)
Space complexity: O(V + E)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| class Solution {
public:
string alienOrder(vector<string> &words) {
unordered_map<char, unordered_set<char>> next_letters;
unordered_map<char, int> indegree;
// Register every letter.
for (const string &word : words) {
for (char letter : word) {
indegree[letter] = 0;
}
}
// Build ordering constraints from adjacent words.
for (int i = 1, n = words.size(); i < n; ++i) {
const string &prev_word = words[i - 1];
const string &curr_word = words[i];
// Invalid prefix case: "abc" before "ab".
if (prev_word.size() > curr_word.size() &&
prev_word.substr(0, curr_word.size()) == curr_word) {
return "";
}
int len = min(prev_word.size(), curr_word.size());
for (int j = 0; j < len; ++j) {
if (prev_word[j] != curr_word[j]) {
char prev_letter = prev_word[j];
char curr_letter = curr_word[j];
// prev_letter must come before curr_letter.
if (!next_letters[prev_letter].contains(curr_letter)) {
next_letters[prev_letter].insert(curr_letter);
++indegree[curr_letter];
}
break;
}
}
}
queue<char> ready_letters;
for (const auto &[letter, degree] : indegree) {
if (degree == 0) {
ready_letters.push(letter);
}
}
string order;
while (!ready_letters.empty()) {
char letter = ready_letters.front();
ready_letters.pop();
order.push_back(letter);
for (char next_letter : next_letters[letter]) {
if (--indegree[next_letter] == 0) {
ready_letters.push(next_letter);
}
}
}
return order.size() == indegree.size() ? order : "";
}
};
|