廣度優先搜尋 (BFS)

破題

這個問題要找出最短的轉換序列長度，當我們看到「最短」時，我們可以想到使用「廣度優先搜尋」來解決。但是，這個問題並沒有直接我們圖，所以我們需要將其抽象化為一張圖。

我們可以將每個單字視為一個節點。如果兩個單字只需改變一個字母就能互相轉換，那麼我們就可以說他們之間存在一條雙向邊。因此，只要找出所有可以進行轉換的單字並將它們連接起來，我們就可以形成一張圖。

有了這張圖，我們就可以從 beginWord（起點）開始，以 endWord（終點）進行廣度優先搜尋，找出從 beginWord 到 endWord 的最短路徑。

跟一流的人才幹大事，享受成功進步的高級樂趣！
內推機會來啦！能與優秀的程式設計師共事，是特別痛快的事，因為厲害的工程師大神會刺激你想要迎頭趕上的上進心，尤其是一起討論解決方案時，他們會觸發你有更好的解決思維能力，彼此共同成長並且一起享受解謎與破關般的樂趣。 你一定聽得懂我在說甚麼感覺，趕快把握機會，動動手指投遞履歷吧！ 立即加入「面試讀書會」，和大家一起準備面試！

內推機會	加入讀書會 (邀請碼：5914)

解題思路

首先，我們需要紀錄每個單字可能的轉換型態，也就是 variation。例如，對於單字 hit，我們可以宣告三個 key： -it、h-t、hi-，並將 hit 連接到這三個 key 上。如果一個單字可以透過改變一個字母轉換為 hit，那麼這個單字就會連接到其中一個 key 上。

接著，我們需要建圖。我們將 beginWord 和 wordList 中的所有單字都加入這個 mapping 中。

最後，我們從 beginWord 開始進行廣度優先搜尋。當我們搜尋到 endWord 時，我們就找到了最短路徑的長度。 要特別注意的是，起點的深度是 1。

程式

class Solution {
    fun ladderLength(beginWord: String, endWord: String, wordList: List<String>): Int {
        val words = buildWords(wordList)
        val queue: Queue<Pair<String, Int>> = LinkedList()
        val visited = mutableSetOf<String>()
        queue.offer(beginWord to 1)
        visited.add(beginWord)
        while (queue.isNotEmpty()) {
            for (j in queue.indices) {
                val (word, depth) = queue.poll()
                if (word == endWord) return depth
                for (i in word.indices) {
                    val variation = word.substring(0, i) + "-" + word.substring(i + 1, word.length)
                    words[variation]?.let { list ->
                        list.forEach { nextWord ->
                            if (!visited.contains(nextWord)) {
                                visited.add(nextWord)
                                queue.offer(nextWord to depth + 1)
                            }
                        }
                    }
                }

            }
        }
        return 0
    }

    private fun buildWords(wordList: List<String>): Map<String, List<String>> {
        val map = mutableMapOf<String, List<String>>()
        wordList.forEach { word ->
            map.putIfAbsent(word, emptyList())
            for (i in word.indices) {
                val variation = word.substring(0, i) + "-" + word.substring(i + 1, word.length)
                map[variation] = (map[variation]?.toMutableList() ?: mutableListOf()) + word
            }
        }
        return map
    }
}

複雜度分析

• 時間複雜度:
  ，其中 是 wordList 的長度， 是列表中單字的長度。

  • 在建圖的過程中，我們需要對每個單字進行操作。每個單字都需要連接到所有可能的轉換型態 (key)，這個過程的時間複雜度是 。然後，我們需要將這些單字加入到 hash table 中，這個過程的時間複雜度是 。所以，建立圖的總時間複雜度是 。
  • 在進行廣度優先搜尋時，最壞情況下的時間複雜度是 。因為每個單字都需要擴展出 個轉換型態 (key)，所以總共有 個節點。

• 空間複雜度:
  ，其中 是 wordList 的長度， 是列表中單字的長度。hash table 中包含了 個節點，每個節點都佔用了 的空間。所以，總的空間複雜度是 。

　更多 LeetCode 解答在此，一起來學習！

內推機會來啦！

跟一流的人才幹大事，享受成功進步的高級樂趣！

內推機會	加入讀書會 (邀請碼：5914)