Problem overview
An alien language uses the lowercase English letters in an order you don't know. The function alienOrder gets an Array<String> named words, sorted in that alien alphabetical order, and returns a string with every letter that appears in the words, each once, in the alien order.
Words are compared as in any dictionary: at the first position where two words differ, the word with the earlier letter comes first. If one word is a prefix of the other, the shorter one comes first, so "ab" is always before "abc". If the words contradict themselves and no letter order could make them sorted, return "". If several orders work, return 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". For ["z", "x", "z"] it is "", because "z" before "x" and "x" before "z" can't both hold. For ["cb", "ca"] it is "bac": the words only say that b comes before a, and of the orders that respect this, "bac" is first alphabetically.
Approach
A sorted list of words tells you facts about letters. Compare two neighbouring words, find the first position where they differ, and the letter in the first word comes before the letter in the second. Letters after that position tell you nothing. Neighbouring pairs are enough: if each word is in order with the next, the whole list is sorted, so other pairs add no new facts.
Draw each fact as an arrow from one letter to another. An order that agrees with every arrow is a topological order of this graph, and Kahn's algorithm finds one: keep an in-degree for each letter (how many letters must come before it that aren't placed yet), and place a letter once its count reaches 0. Placing a letter lowers the count of the letters it points to.
Two extra rules are specific to this problem:
- Prefix contradiction. If a longer word comes right before its own prefix (
"abc"then"ab"), the list can't be sorted in any alphabet. The function returns"". - Cycles. If, at some point, letters are still waiting but none has an in-degree of 0, they wait for each other. That is a cycle, and the function returns
"".
To get the alphabetically first answer, each round takes the smallest ready letter instead of any ready letter. With at most 26 letters, scanning from a to z each round is cheap. Building the graph looks at each letter of the input a bounded number of times, so the time is O(C), where C is the total number of letters in words. Comparing every pair of words would take O(n²) comparisons for n words.
Step by step
- Find the letters that appear.
waitingis aBooleanArray(26), one entry per letter, all false at first.waiting[k]becomes true when letter numberkappears in the words, and goes back to false when the letter is placed in the answer. An array indexed by letter is simpler than a map for 26 letters. - Count them.
var letters = 0counts the different letters, so the answer is complete when its length reachesletters. - Visit every character. An outer loop over
wordsand an inner loop over the characterscof eachword. - Mark each letter once.
if (!waiting[c - 'a'])is true the first time a letter appears. Subtracting twoCharvalues gives anInt, soc - 'a'is 0 for a through 25 for z. Inside, set the entry to true and doletters++. - Create the graph.
Array(26) { mutableListOf<Int>() }makes one list per letter, with its own list each time because the lambda runs once per index.graph[a]holds the letters that must come aftera. - Create the in-degrees.
IntArray(26)starts at zeros.inDegree[b]counts the arrows pointing atb. - Loop over neighbouring pairs.
for (i in 0 until words.size - 1), withfirst = words[i]andsecond = words[i + 1]. - Find the first difference.
var j = 0and awhileloop that advances whilejis inside both words andfirst[j] == second[j]. The checks run left to right, so the characters are read only whilejis valid. - Add the arrow. If
jis still inside both words,first[j]andsecond[j]differ: addsecond[j] - 'a'tograph[first[j] - 'a']and doinDegree[second[j] - 'a']++. If two pairs give the same arrow, it is counted twice here and removed twice later, which stays consistent. - Catch the prefix case. Otherwise one word ran out. If
first.length > second.length, the second is a prefix of the first and comes after it: return"". An equal or shorter first word gives no fact. - Run Kahn's algorithm.
var order = ""collects the answer, andwhile (order.length < letters)places one letter per round. - Find the smallest ready letter. Start
var letter = 0and advance whileletter < 26 && (!waiting[letter] || inDegree[letter] > 0). A letter is ready when it appears in the words, isn't placed yet, and every letter before it is placed. - Detect a cycle. If
letter == 26, nothing is ready: return"". - Place the letter. Set
waiting[letter] = falseand append'a' + lettertoorder. - Release the letters after it. For each
nextLetteringraph[letter], doinDegree[nextLetter]--. - Return the order. Every letter was placed after all the letters that must precede it.
The solution in Kotlin
class Solution {
fun alienOrder(words: Array<String>): String {
val waiting = BooleanArray(26)
var letters = 0
for (word in words) {
for (c in word) {
if (!waiting[c - 'a']) {
waiting[c - 'a'] = true
letters++
}
}
}
val graph = Array(26) { mutableListOf<Int>() }
val inDegree = IntArray(26)
for (i in 0 until words.size - 1) {
val first = words[i]
val second = words[i + 1]
var j = 0
while (j < first.length && j < second.length && first[j] == second[j]) {
j++
}
if (j < first.length && j < second.length) {
graph[first[j] - 'a'].add(second[j] - 'a')
inDegree[second[j] - 'a']++
} else if (first.length > second.length) {
return ""
}
}
var order = ""
while (order.length < letters) {
var letter = 0
while (letter < 26 && (!waiting[letter] || inDegree[letter] > 0)) {
letter++
}
if (letter == 26) {
return ""
}
waiting[letter] = false
order += 'a' + letter
for (nextLetter in graph[letter]) {
inDegree[nextLetter]--
}
}
return order
}
}
Kotlin details worth knowing:
- Char arithmetic.
Char - Charis anInt, andChar + Intis aChar. So'c' - 'a'is2and'a' + 2is'c'. That is how the code moves between letters and indexes. - String plus Char.
order += 'a' + letterbuilds theCharfirst and then appends it to the string. The expression"w" + ('a' + 2)gives"wc". for (c in word)iterates over the characters of a string directly.Array(26) { mutableListOf<Int>() }creates 26 separate lists. Filling an array with one shared list would make every letter point at the same list.x++on an array element, as ininDegree[b]++, works on avalarray because only its contents change.
Complexity
The first pass reads every letter once. Comparing neighbouring words reads each word at most twice, so that part is O(C) too. Kahn's algorithm places at most 26 letters, scanning at most 26 entries each time, and walks each arrow once, so that part is bounded by a constant plus the number of pairs. The total is O(C) time, treating the 26-letter alphabet as a constant. The extra space is O(1) for the fixed-size arrays, plus at most one arrow per neighbouring pair in the lists.
Edge cases and common mistakes
- A longer word before its prefix.
["abc", "ab"]returns"", while["ab", "abc"]returns"abc". - Cycles.
["z", "x", "z"]returns"", as does["a", "b", "a"]. - Letters without any arrow. They still belong in the answer.
["abc"]gives"abc", and in["cb", "ca"]the letterchas no arrow but is placed in alphabetical position. - Several valid orders. Always take the smallest ready letter.
["zy", "zx"]gives"yxz", becauseymust come beforexandzis free but alphabetically last. - Repeated words.
["x", "x", "x"]gives"x": equal neighbours give no arrow and no contradiction. - Using a cycle-blind approach. A DFS that doesn't track "in progress" nodes may loop or return a wrong order for contradictory input.
- Reading past a word's end. Compare
jwith both lengths before readingfirst[j]andsecond[j]. - Counting letters from the arrows only. A letter that appears in no differing position would be dropped. That's why the first pass collects letters from all the words.
Testing
Results from running the solution:
["wrt", "wrf", "er", "ett", "rftt"]:"wertf"["z", "x", "z"]:""["cb", "ca"]:"bac"["abc", "ab"]:""["ab", "abc"]:"abc"["z", "z"]:"z"["zy", "zx"]:"yxz"["ba", "bc", "ac", "cab"]:"bac"["ab", "adc"]:"abcd"
