269. Alien Dictionary

Hard

Description

給定一組按照外星語言字母順序排列的單字列表 words。推導出該語言的字母順序。若順序不合法回傳空字串，若有多種合法順序回傳任意一種。

Example:

Input: words = [“wrt”,“wrf”,“er”,“ett”,“rftt”] Output: “wertf”

Intuition#

從相鄰單字的第一個不同字元推導字母先後關係（有向邊），再做拓撲排序。

比較相鄰的兩個單字，找出第一個不同的字元，就確定了一條順序關係（邊）
注意特殊情況：若較長的單字是較短單字的前綴（如 "abc" 在 "ab" 前面），則順序不合法
所有邊建好後做拓撲排序，若有環則不合法

Approaches#

1: DFS 拓撲排序#

概念: 建立有向圖，DFS 後序反轉得到拓撲排序，用三色標記偵測環
時間複雜度: O(C)，C = 所有單字的總字元數
空間複雜度: 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 拓撲排序（Kahn’s Algorithm）#

概念: 計算入度，從入度為 0 的字元開始 BFS，出隊順序即為字母順序
時間複雜度: O(C)
空間複雜度: 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: 從排序推導偏序關係 + 拓撲排序
關鍵技巧: 只有相鄰單字的第一個不同字元能推導順序；別忘了處理前綴異常情況（"abc" 在 "ab" 前面是不合法的）