LeetCode - Word Ladder（單詞接龍）

題目描述

給定兩個單詞 beginWord 和 endWord，以及一個字典列表 wordList。你的目標是將 beginWord 逐步轉換為 endWord，每次轉換只能改變單詞中的一個字母，並且轉換後的單詞必須存在於 wordList 中。求出從 beginWord 到 endWord 的最短轉換序列的長度。如果無法到達 endWord，返回 0。

範例：

輸入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
輸出：5
解釋：最短轉換序列為 "hit" -> "hot" -> "dot" -> "dog" -> "cog"，一共 5 步。

輸入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
輸出：0
解釋："cog" 不在 wordList 中，因此無法完成轉換。

解法思路

這個問題可以視為圖中的最短路徑問題，每個單詞是一個節點，相鄰單詞之間有邊連接。要找出最短的轉換步驟數，我們可以使用廣度優先搜索（BFS）。

1. 將字典轉換為集合：方便快速查找單詞是否在 wordList 中。
2. 檢查目標單詞：如果 endWord 不在 wordList 中，直接返回 0。
3. BFS 遍歷：
   • 使用佇列進行層級遍歷，從 beginWord 開始，逐層轉換單詞。
   • 對於當前單詞的每個字母，嘗試用 a-z 的所有字母替換一次，檢查是否在 wordList 中。
   • 如果替換後的單詞在 wordList 中，將其加入佇列並標記為已訪問。
4. 返回結果：當到達 endWord 時，返回當前層數作為步驟數；若佇列結束仍未找到，返回 0。

範例代碼

以下是 Python 的實現：

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    word_set = set(wordList)  # 將 wordList 轉換為集合
    if endWord not in word_set:
        return 0

    queue = deque([(beginWord, 1)])  # 初始化佇列，包含單詞和步驟數

    while queue:
        current_word, steps = queue.popleft()

        # 遍歷當前單詞的每個位置
        for i in range(len(current_word)):
            # 嘗試替換字母 a-z
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = current_word[:i] + c + current_word[i+1:]
                
                # 找到終點單詞
                if next_word == endWord:
                    return steps + 1

                # 如果替換後單詞在 word_set 中
                if next_word in word_set:
                    queue.append((next_word, steps + 1))
                    word_set.remove(next_word)  # 將已訪問的單詞移除

    return 0

代碼解析

1. 初始化集合和佇列：將 wordList 轉為集合 word_set，初始化佇列 queue，存放當前單詞和步驟數。
2. BFS 遍歷：從 beginWord 開始，每次取出當前單詞，生成所有可能的相鄰單詞。
   • 如果生成的單詞是 endWord，則返回步驟數加 1。
   • 若相鄰單詞在 word_set 中，將其加入佇列並標記為已訪問。
3. 無法找到：若 BFS 結束後無法找到 endWord，返回 0。

時間和空間複雜度

• 時間複雜度：O(M * N)，其中 M 是單詞的長度，N 是 wordList 中的單詞數量。每個單詞有 M 個位置，每個位置的字母可以替換 26 次。
• 空間複雜度：O(M * N)，用於存儲 wordList 的集合和佇列中的單詞。