LeetCode 127：單詞接龍

問題本質：最短轉換序列的長度

給定兩個單詞 beginWord 和 endWord，以及字典 wordList，要求找到從 beginWord 到 endWord 的最短轉換序列（每次轉換僅改變一個字母，且中間單詞必須在 wordList 中），返回序列的單詞數；若無法轉換，返回 0。

核心思路：廣度優先搜索（BFS）

BFS 天然適合解決最短路徑問題，因為它按層次遍歷，第一次到達目標節點時的層數即為最短路徑長度。

關鍵觀察：

1. 鄰居生成：每個單詞的“鄰居”是改變一個字母后得到的所有可能單詞（需在 wordList 中）。
2. 去重處理：用集合記錄已訪問的單詞，避免重復處理（否則會導致無限循環或超時）。

算法步驟詳解

步驟 1：預處理與邊界檢查

• 將 wordList 轉換為 HashSet，確保查找時間為 O(1)。
• 若 endWord 不在 wordList 中，直接返回 0（無法轉換）。

步驟 2：初始化 BFS

• 隊列：存儲當前處理的單詞及當前步數（通過分層遍歷實現，隊列中同一層的單詞對應相同步數）。
• 訪問集合：記錄已處理的單詞，避免重復入隊。
• 初始狀態：將 beginWord 入隊，步數為 1（beginWord 是序列的第一個單詞）。

步驟 3：分層遍歷（BFS 核心）

1. 遍歷當前層：每次取出隊列中當前層的所有單詞（通過 queue.size() 獲取層大小）。
2. 生成鄰居：對每個單詞，遍歷其每個字符位置，嘗試替換為 a-z 中除原字符外的所有可能，生成新單詞。
3. 檢查終止條件：若新單詞是 endWord，直接返回 當前步數 + 1（新單詞是下一層，步數加1）。
4. 合法鄰居入隊：若新單詞在 wordList 中且未被訪問，標記為已訪問并加入隊列。

步驟 4：處理剩余情況

若遍歷完所有可能仍未找到 endWord，返回 0。

完整代碼（Java）

import java.util.*;class Solution {public int ladderLength(String beginWord, String endWord, List<String> wordList) {// 1. 預處理：轉換為集合，加速查找Set<String> wordSet = new HashSet<>(wordList);// 邊界檢查：endWord 不在字典中，直接返回 0if (!wordSet.contains(endWord)) {return 0;}// 2. 初始化 BFS：隊列（存儲單詞）、訪問集合、步數Queue<String> queue = new LinkedList<>();Set<String> visited = new HashSet<>();queue.offer(beginWord);visited.add(beginWord);int step = 1; // beginWord 是第一個單詞，步數初始為 1// 3. 分層遍歷while (!queue.isEmpty()) {int currentLevelSize = queue.size(); // 當前層的單詞數量for (int i = 0; i < currentLevelSize; i++) {String currentWord = queue.poll();// 生成所有可能的鄰居（改變一個字母）for (int j = 0; j < currentWord.length(); j++) {// 嘗試替換為 a-z 中除原字符外的所有字母for (char c = 'a'; c <= 'z'; c++) {if (c == currentWord.charAt(j)) {continue; // 跳過原字符，保證只改變一個字母}// 構造新單詞StringBuilder sb = new StringBuilder(currentWord);sb.setCharAt(j, c);String newWord = sb.toString();// 終止條件：找到 endWord，返回步數+1if (newWord.equals(endWord)) {return step + 1;}// 合法鄰居：在字典中且未被訪問if (wordSet.contains(newWord) && !visited.contains(newWord)) {visited.add(newWord);queue.offer(newWord);}}}}step++; // 處理完當前層，步數加 1}// 4. 遍歷結束仍未找到，返回 0return 0;}
}

關鍵細節解析

1. 鄰居生成優化：
   對每個字符位置，遍歷 26 個字母（跳過原字符），確保僅改變一個字母。時間復雜度為 O(L×26)（L 是單詞長度，最多為 10），高效可控。

2. 分層遍歷的意義：
   通過 queue.size() 分層處理，保證每次處理的是同一步數的單詞，確保第一次到達 endWord 時的步數是最小值。

3. 去重的必要性：
   若不標記已訪問，同一單詞可能被多次入隊，導致時間復雜度過高（例如，hot 可能被不同路徑多次生成）。

復雜度分析

• 時間復雜度：O(N×L×26)，其中 N 是 wordList 的長度（最多 5000），L 是單詞長度（最多 10）。每個單詞生成 L×25 個鄰居（排除原字符），整體可接受。
• 空間復雜度：O(N)，隊列和訪問集合最多存儲 N 個單詞。

示例驗證

示例 1：

• 輸入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
• 過程：hit → hot → dot → dog → cog，共 5 步。代碼中，當處理 dog 時生成 cog，返回 step + 1 = 4 + 1 = 5，符合預期。

示例 2：

• 輸入：endWord 不在 wordList 中，直接返回 0。

該方案通過 BFS 層次遍歷 高效求解最短路徑，利用集合優化查找和去重，確保了算法的正確性與性能，是處理“單詞接龍”類問題的經典思路。