題目
#

題目簡述
#

給定兩個單詞（beginWord 和 endWord）和一個單詞字典 wordList，找出從 beginWord 到 endWord 的最短轉換序列長度。每次只能改變一個字符，且新單詞必須在 wordList 中。

範例
#

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: 一個最短的轉換序列是 "hit" → "hot" → "dot" → "dog" → "cog"，長度為 5 個單詞。

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: 終點單詞 "cog" 不在單詞列表中，因此沒有有效的轉換序列。

解題思路
#

這題要求我們找到從 beginWord 到 endWord 的最短轉換序列長度。每次只能改變一個字符，且新單詞必須在 wordList 中。

我們可以用BFS從 beginWord 開始，逐層向外擴展，直到找到 endWord。

解法
#

使用 BFS 來解決：

首先將 wordList 轉換為 HashSet 以便快速查找。
檢查 endWord 是否在 wordList 中，如果不在則返回 0。
使用隊列進行 BFS，從 beginWord 開始。
對於每個單詞，嘗試改變每個位置的字符（a-z）。
如果新單詞在 wordList 中，加入隊列並從集合中移除（避免重複訪問）。
每層代表一個轉換步驟，距離從 1 開始計算。

例子說明
#

beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]

初始情況：queue = ["hit"], distance = 1

第一層（距離 = 1）：
- 處理 “hit”
- 嘗試改變每個字符：
  - “ait”, “bit”, …, “zit” → 都不在 wordList 中
  - “hat”, “hbt”, …, “hot” → “hot” 在 wordList 中，加入隊列
  - “hia”, “hib”, …, “hiz” → 都不在 wordList 中
- 隊列更新為：["hot"]
第二層（距離 = 2）：
- 處理 “hot”
- 嘗試改變每個字符：
  - “aot”, “bot”, …, “zot” → 都不在 wordList 中
  - “hat”, “hbt”, …, “hzt” → 都不在 wordList 中
  - “hoa”, “hob”, …, “hoz” → 都不在 wordList 中
- 隊列更新為：[]
第三層（距離 = 3）：
- 處理 “dot”
- 嘗試改變每個字符：
  - “aot”, “bot”, …, “zot” → 都不在 wordList 中
  - “dat”, “dbt”, …, “dzt” → 都不在 wordList 中
  - “doa”, “dob”, …, “dog” → “dog” 在 wordList 中，加入隊列
- 隊列更新為：["dog"]
第四層（距離 = 4）：
- 處理 “dog”
- 嘗試改變每個字符：
  - “aog”, “bog”, …, “cog” → “cog” 在 wordList 中，且是目標單詞
- 找到目標，返回距離 5

完整程式碼
#

java

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        // 建立單詞集合以便快速查找
        Set<String> wordSet = new HashSet<>(wordList);

        // 如果終點單詞不在單詞列表中，無法轉換
        if (!wordSet.contains(endWord)) {
            return 0;
        }

        // 使用隊列進行廣度優先搜索
        Queue<String> wordQueue = new LinkedList<>();

        // 從起始單詞開始 BFS
        wordQueue.add(beginWord);

        // 距離從 1 開始（包含起始單詞）
        int distance = 1;

        // BFS 循環：直到隊列為空
        while (!wordQueue.isEmpty()) {
            int size = wordQueue.size(); // 當前層的節點數量

            // 處理當前層級的所有單詞
            for (int i = 0; i < size; i++) {
                String currWord = wordQueue.poll(); // 取出隊首單詞

                // 如果當前單詞是終點單詞，返回距離
                if (currWord.equals(endWord)) {
                    return distance;
                }

                // 嘗試改變當前單詞的每個字符
                for (int j = 0; j < currWord.length(); j++) {
                    char[] temp = currWord.toCharArray(); // 轉換為字符數組

                    // 將位置 j 的字符替換為 a-z 中的每個字母
                    for (char c = 'a'; c <= 'z'; c++) {
                        temp[j] = c;
                        String newWord = new String(temp); // 構建新單詞

                        // 如果新單詞在單詞集合中，加入隊列
                        if (wordSet.contains(newWord)) {
                            wordQueue.add(newWord); // 加入隊列
                            wordSet.remove(newWord); // 移除以避免重複訪問
                        }
                    }
                }
            }

            // 處理完當前層級後增加距離
            distance++;
        }

        // 如果沒有找到轉換序列，返回 0
        return 0;
    }
}