給定一組按照外星語言字母順序排列的單字列表
words。推導出該語言的字母順序。若順序不合法回傳空字串，若有多種合法順序回傳任意一種。
Example:
Input: words = [“wrt”,“wrf”,“er”,“ett”,“rftt”] Output: “wertf”
Intuition
TIP
從相鄰單字的第一個不同字元推導字母先後關係（有向邊），再做拓撲排序。
- 比較相鄰的兩個單字，找出第一個不同的字元，就確定了一條順序關係（邊）
- 注意特殊情況：若較長的單字是較短單字的前綴（如
"abc"在"ab"前面），則順序不合法 - 所有邊建好後做拓撲排序，若有環則不合法
Approaches
1. DFS Topological Sort — O(C) / O(U + min(U^2, N))
- Idea: 建立有向圖，DFS 後序反轉得到拓撲排序，用三色標記偵測環
- Time:
O(C)，C = 所有單字的總字元數 - Space:
O(U + min(U^2, N))，U = 唯一字元數，N = 單字數
class Solution {
fun alienOrder(words: Array<String>): String {
val graph = HashMap<Char, MutableSet<Char>>()
for (word in words) {
for (c in word) graph.putIfAbsent(c, mutableSetOf())
}
for (i in 0 until words.size - 1) {
val w1 = words[i]
val w2 = words[i + 1]
if (w1.length > w2.length && w1.startsWith(w2)) return ""
for (j in 0 until minOf(w1.length, w2.length)) {
if (w1[j] != w2[j]) {
graph[w1[j]]!!.add(w2[j])
break
}
}
}
val state = HashMap<Char, Int>() // 0: unvisited, 1: visiting, 2: visited
val result = StringBuilder()
fun dfs(c: Char): Boolean {
if (state.getOrDefault(c, 0) == 1) return false // cycle
if (state.getOrDefault(c, 0) == 2) return true
state[c] = 1
for (next in graph[c]!!) {
if (!dfs(next)) return false
}
state[c] = 2
result.append(c)
return true
}
for (c in graph.keys) {
if (!dfs(c)) return ""
}
return result.reverse().toString()
}
}⭐ 2. BFS Topological Sort (Kahn's) — O(C) / O(U + min(U^2, N))
- Idea: 計算入度，從入度為 0 的字元開始 BFS，出隊順序即為字母順序
- Time:
O(C) - Space:
O(U + min(U^2, N))
class Solution {
fun alienOrder(words: Array<String>): String {
val graph = HashMap<Char, MutableSet<Char>>()
val inDegree = HashMap<Char, Int>()
for (word in words) {
for (c in word) {
graph.putIfAbsent(c, mutableSetOf())
inDegree.putIfAbsent(c, 0)
}
}
for (i in 0 until words.size - 1) {
val w1 = words[i]
val w2 = words[i + 1]
if (w1.length > w2.length && w1.startsWith(w2)) return ""
for (j in 0 until minOf(w1.length, w2.length)) {
if (w1[j] != w2[j]) {
if (w2[j] !in graph[w1[j]]!!) {
graph[w1[j]]!!.add(w2[j])
inDegree[w2[j]] = inDegree.getOrDefault(w2[j], 0) + 1
}
break
}
}
}
val queue: ArrayDeque<Char> = ArrayDeque()
for ((c, deg) in inDegree) {
if (deg == 0) queue.add(c)
}
val result = StringBuilder()
while (queue.isNotEmpty()) {
val c = queue.removeFirst()
result.append(c)
for (next in graph[c]!!) {
inDegree[next] = inDegree[next]!! - 1
if (inDegree[next] == 0) queue.add(next)
}
}
return if (result.length == inDegree.size) result.toString() else ""
}
}🔑 Takeaways
- Pattern: 從排序推導偏序關係 + 拓撲排序
- Key trick: 只有相鄰單字的第一個不同字元能推導順序；別忘了處理前綴異常情況（
"abc"在"ab"前面是不合法的）