Problem overview
The function alienOrder receives a vector<string> called words, which is sorted in an alien alphabet. Words compare as in any dictionary: at the first position where they differ, the word with the earlier letter comes first. When one word is a prefix of the other, the shorter one comes first, so "ab" always comes before "abc".
The function returns a string with every letter that appears in words, each once, in the order of the alien alphabet. If the words contradict themselves, so that no order of the letters makes them sorted, it returns the empty string. If several orders work, it returns the one that comes first in the usual alphabetical order, which makes the answer unique.
For {"wrt", "wrf", "er", "ett", "rftt"} the answer is "wertf". Each pair of neighbouring words gives one fact from the first letters where they differ: t before f, w before e, r before t, e before r. Chained, that is w, e, r, t, f. For {"z", "x", "z"} the answer is "", because z before x and x before z form a cycle. For {"cb", "ca"} the only fact is b before a. The orders "bac", "bca" and "cba" all work, and "bac" comes first alphabetically.
Approach: turn the facts into arrows
Every fact is an arrow between two letters: the first points to the second, meaning it must come earlier. An order that agrees with every arrow is a topological order of this graph, and Kahn's algorithm finds one. It tracks for each letter its in-degree, the number of letters that must come before it and aren't placed yet. A letter with in-degree 0 can be placed at once. Placing it removes its arrows, which may free other letters.
Only neighbouring words need to be compared. If every word is in order with the next one, the whole list is sorted, so other pairs add no new facts. For a pair, find the first position where the words differ. If there is one, the letters there give one arrow, and the letters after that position say nothing. If there is none, one word is a prefix of the other. When the earlier word is the longer one, the list is impossible in any alphabet, so the answer is "".
To get the alphabetically first order, each round of Kahn's algorithm takes the smallest letter that is ready, scanning from a to z. A letter is ready when it appears in the words, isn't placed yet, and has in-degree 0. If letters remain but none is ready, each waits for another waiting letter. That is a cycle, so the answer is "".
The cost depends on the total number of letters, C: one pass over the words finds the letters, and one comparison per neighbouring pair stops at the first difference. Comparing every pair of words would take O(n²) comparisons for n words.
Step by step
- Mark the letters that appear. A
vector<bool>namedwaitingof 26falsevalues, one per letter.waiting[k]is true while letterkappears in the words and isn't in the answer yet. - Count them in an
intnamedletters. The answer is complete when its length reaches this number. - Loop over each word and each character. When
!waiting[c - 'a'], set it totrueand increaseletters. Because a to z are consecutive,c - 'a'is 0 foraup to 25 forz, and the test makes each letter count once. - Create the graph: a
vector<vector<int>>namedgraphwith 26 empty vectors.graph[a]holds the letters that must come aftera. - Create
inDegree, 26 zeros. - Loop over neighbouring pairs,
words[i]andwords[i + 1], copied into stringsfirstandsecond. - Find the first difference. Start
jat 0 and advance it while it is inside both words andfirst[j] == second[j]. - Record the arrow when
jis still inside both words: push the index ofsecond[j]ontographat the index offirst[j]and increase the in-degree ofsecond[j]. Two pairs may give the same arrow. Each copy is counted here and removed once later, so that is fine. - Catch the prefix case with
else if (first.size() > second.size()), and return"". - Create
order, an empty string. - Loop while
order.size() < letters. Each round places one letter. - Find the smallest ready letter. Start
letterat 0 and advance it whileletter < 26and the letter isn't waiting or still has arrows coming in. - Detect a cycle. If
letter == 26, nothing is ready: return"". - Place the letter. Set
waiting[letter]tofalseand append(char) ('a' + letter)toorder. - Release its successors. For every
nextLetteringraph[letter], decreaseinDegree[nextLetter]. - Return
order.
The solution in C++
class Solution {
public:
string alienOrder(vector<string>& words) {
vector<bool> waiting(26, false);
int letters = 0;
for (string& word : words) {
for (char c : word) {
if (!waiting[c - 'a']) {
waiting[c - 'a'] = true;
letters++;
}
}
}
vector<vector<int>> graph(26);
vector<int> inDegree(26, 0);
for (int i = 0; i < words.size() - 1; i++) {
string first = words[i];
string second = words[i + 1];
int j = 0;
while (j < first.size() && j < second.size() && first[j] == second[j]) {
j++;
}
if (j < first.size() && j < second.size()) {
graph[first[j] - 'a'].push_back(second[j] - 'a');
inDegree[second[j] - 'a']++;
} else if (first.size() > second.size()) {
return "";
}
}
string order = "";
while (order.size() < letters) {
int letter = 0;
while (letter < 26 && (!waiting[letter] || inDegree[letter] > 0)) {
letter++;
}
if (letter == 26) {
return "";
}
waiting[letter] = false;
order += (char) ('a' + letter);
for (int nextLetter : graph[letter]) {
inDegree[nextLetter]--;
}
}
return order;
}
};
The C++ details worth a closer look:
- Characters are numbers.
c - 'a'is anint, which indexes the vectors. Going back,'a' + letteris also anint, so(char)turns it into a character before it is appended. Without the cast,order += 'a' + letterwould still compile, because the sum is converted back tocharwhen appended, but the cast makes the intention clear. words.size() - 1is unsigned. For a vector with one word it is 0, and the loop doesn't run. For an empty vector it would wrap to a huge number, but the statement guarantees at least one word. The comparisoni < words.size() - 1mixes anintwith an unsigned value, which is harmless whileiis not negative.vector<vector<int>> graph(26)creates 26 empty inner vectors.vector<bool> waiting(26, false)takes a size and then the value of every element.- Short-circuit order. In the
whileoverj, the two size checks come beforefirst[j] == second[j], so the characters are read only whilejis inside both words. In the scan for a ready letter,letter < 26is checked first, so index 26 is never read. string first = words[i]copies the word. The words are at most 20 characters, so the copy is cheap, and aconst string&would also do.
Complexity
Time: O(C), where C is the total number of letters in words. Collecting the letters visits each character once. Comparing neighbouring pairs costs at most the length of the shorter word each. Kahn's algorithm runs at most 26 rounds, each scanning 26 letters, plus one decrease per arrow, and there is at most one arrow per neighbouring pair.
Space: O(n) for n words. The vectors of size 26 are constant. The only part that grows is the list of arrows, at most one per neighbouring pair of words.
Edge cases and common mistakes
- A prefix in the wrong order.
{"abc", "ab"}gives"". The longer word comes first, which no alphabet allows. - A prefix in the right order.
{"ab", "abc"}gives no arrow, and the letters come out as"abc". - Equal words.
{"ab", "ab"}gives"ab": no letter differs, and the first word is not longer. - A single word.
{"a"}gives"a": there are no pairs and one letter to place. - Unconstrained letters. They are still part of the answer. With
{"cb", "ca"}the letterchas no arrow, yet it appears in"bac". - A contradiction.
{"z", "x", "z"}gives"": both z and x wait for each other. - Comparing beyond the first difference. Only the first differing letters say anything. The letters after them are unconstrained.
- Skipping the smallest-first rule. Another queue order would still be a valid topological order, but the lesson asks for the alphabetically first one. The scan from
atozguarantees it.
Testing
{"wrt", "wrf", "er", "ett", "rftt"}gives"wertf".{"z", "x", "z"}gives"".{"cb", "ca"}gives"bac".{"abc", "ab"}gives"".{"a"}gives"a".{"ab", "ab"}gives"ab".{"b", "a", "c"}gives"bac".{"ba", "bc", "ac", "cab"}gives"bac".
