127. Word Ladder

Hard

Description

給定 beginWord、endWord 和一個字典 wordList。每次變換可以改變一個字母，且變換後的單字必須在字典中。回傳從 beginWord 到 endWord 的最短變換序列長度。若無法到達，回傳 0。

Example:

Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”] Output: 5 (hit -> hot -> dot -> dog -> cog)

Intuition#

將每個單字視為圖的節點，只差一個字母的單字之間有邊，BFS 找最短路徑。

隱式圖：節點是單字，邊是一個字母的差異
BFS 天然適合找無權圖的最短路徑
關鍵是如何高效找到鄰居：用通配符模式 (wildcard pattern) 建立映射

Approaches#

1: BFS（逐字元嘗試 a-z）#

概念: 對當前單字的每個位置嘗試替換 a-z，檢查是否在字典中
時間複雜度: O(m^2 * n)，m = 單字長度，n = 字典大小
空間複雜度: O(m * n)

class Solution {
    fun ladderLength(beginWord: String, endWord: String, wordList: List<String>): Int {
        val wordSet = HashSet(wordList)
        if (endWord !in wordSet) return 0

        val queue: ArrayDeque<String> = ArrayDeque()
        queue.add(beginWord)
        val visited = HashSet<String>()
        visited.add(beginWord)
        var level = 1

        while (queue.isNotEmpty()) {
            val size = queue.size
            repeat(size) {
                val word = queue.removeFirst()
                val chars = word.toCharArray()
                for (i in chars.indices) {
                    val original = chars[i]
                    for (c in 'a'..'z') {
                        if (c == original) continue
                        chars[i] = c
                        val newWord = String(chars)
                        if (newWord == endWord) return level + 1
                        if (newWord in wordSet && newWord !in visited) {
                            visited.add(newWord)
                            queue.add(newWord)
                        }
                    }
                    chars[i] = original
                }
            }
            level++
        }
        return 0
    }
}

⭐2: BFS + 通配符預處理#

概念: 預處理字典，將每個單字映射到其通配符模式（如 h*t），BFS 時透過模式快速找到鄰居
時間複雜度: O(m^2 * n)
空間複雜度: O(m^2 * n)

class Solution {
    fun ladderLength(beginWord: String, endWord: String, wordList: List<String>): Int {
        val wordSet = HashSet(wordList)
        if (endWord !in wordSet) return 0

        val m = beginWord.length
        val patternMap = HashMap<String, MutableList<String>>()

        for (word in wordList) {
            for (i in 0 until m) {
                val pattern = word.substring(0, i) + "*" + word.substring(i + 1)
                patternMap.getOrPut(pattern) { mutableListOf() }.add(word)
            }
        }

        val queue: ArrayDeque<String> = ArrayDeque()
        val visited = HashSet<String>()
        queue.add(beginWord)
        visited.add(beginWord)
        var level = 1

        while (queue.isNotEmpty()) {
            val size = queue.size
            repeat(size) {
                val word = queue.removeFirst()
                for (i in 0 until m) {
                    val pattern = word.substring(0, i) + "*" + word.substring(i + 1)
                    for (neighbor in patternMap.getOrDefault(pattern, emptyList())) {
                        if (neighbor == endWord) return level + 1
                        if (neighbor !in visited) {
                            visited.add(neighbor)
                            queue.add(neighbor)
                        }
                    }
                }
            }
            level++
        }
        return 0
    }
}

補充解法：雙向 BFS

概念: 從 beginWord 和 endWord 兩端同時做 BFS，每次擴展較小的一端，相遇時即找到最短路徑
時間複雜度: O(m^2 * n)（但實際比單向 BFS 快很多）
空間複雜度: O(m * n)

class Solution {
    fun ladderLength(beginWord: String, endWord: String, wordList: List<String>): Int {
        val wordSet = HashSet(wordList)
        if (endWord !in wordSet) return 0

        var beginSet = HashSet<String>()
        var endSet = HashSet<String>()
        beginSet.add(beginWord)
        endSet.add(endWord)
        val visited = HashSet<String>()
        visited.add(beginWord)
        visited.add(endWord)
        var level = 1

        while (beginSet.isNotEmpty() && endSet.isNotEmpty()) {
            if (beginSet.size > endSet.size) {
                val temp = beginSet; beginSet = endSet; endSet = temp
            }
            val nextSet = HashSet<String>()
            for (word in beginSet) {
                val chars = word.toCharArray()
                for (i in chars.indices) {
                    val original = chars[i]
                    for (c in 'a'..'z') {
                        chars[i] = c
                        val newWord = String(chars)
                        if (newWord in endSet) return level + 1
                        if (newWord in wordSet && newWord !in visited) {
                            visited.add(newWord)
                            nextSet.add(newWord)
                        }
                    }
                    chars[i] = original
                }
            }
            beginSet = nextSet
            level++
        }
        return 0
    }
}

🔑 Takeaways#

Pattern: 隱式圖 BFS 最短路徑 – 狀態空間搜尋
關鍵技巧: 通配符模式建立鄰接關係避免 O(n^2) 的兩兩比較；雙向 BFS 可大幅減少搜尋空間