題目與適用情境
給定 beginWord、endWord 和 wordList，求最短轉換序列的長度。相鄰兩個單字必須恰好有一個 位置不同；除了 beginWord，每個單字都必須出現在字典中，endWord 也不例外。回傳值計算 單字數，不是修改次數。
beginWord = "hit"
endWord = "cog"
wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
一條最短序列：
hit -> hot -> dot -> dog -> cog
回傳：5採用標準限制：beginWord 與 endWord 不同；所有單字只含小寫英文字母；字典單字的長度都為 L、互不重複；字典最多有 N = 5,000 個單字。endWord 不在字典中或無法抵達時回傳 0。
這道題把圖藏在字串裡。每個合法單字是一個頂點；兩個單字恰好相差一個字母時，存在一條無向、 單位成本的邊。因此，題目要求在無權圖中尋找單一起點到單一終點的最短路徑。2026 年公開的圖 演算法面試材料仍把單字接龍列為 BFS 轉換題，2026 年 6 月的一份公開面試紀錄也討論了更難的 Word Ladder II。這些材料只能證明本題目前仍有準備價值，不能證明面試頻率或公司歸屬，因此 本文不作這兩類聲稱。
面試官考察重點
第一項訊號是能否辨識隱式圖。逐對比較所有單字可以建出正確的圖，但要做 O(N²) 次比較，每次 花 O(L)。較強的回答只產生目前單字可能存在的鄰居：逐一把每個位置替換成其餘 25 個字母， 再用雜湊集合判斷候選單字是否在字典中。
第二項訊號是最短路徑推導。每次轉換的成本都是一，所以 BFS 按距離非遞減順序搜尋。DFS 最後 可能找到路徑，卻不能保證第一條路徑最短；Dijkstra 對單位權重也正確，但優先佇列沒有提供額外 資訊。
第三項訊號是標記已造訪的時機。單字進入前緣時就必須移出未造訪集合，不能等到之後展開時才 刪除。延遲標記會讓多個父節點重複加入同一個單字，增加時間與記憶體。雙向 BFS 產生候選單字 後，應先檢查它是否位於另一側目前前緣，再檢查未造訪集合。
第四項訊號是能否證明最佳化沒有破壞正確性。雙向 BFS 在兩個端點各維護一個完整層前緣，每次 展開較小的前緣。在近似樹狀、有效分支數為 b、答案邊數為 d 時，實際探索量常從接近 b^d 降到兩次約 b^(d/2) 的搜尋。但它沒有改善最壞漸進上界：對抗字典仍可能讓演算法檢查 幾乎全部單字。
最後還要正確核算字串成本。每個展開的單字最多嘗試 25L 個變體。在 Python 中，建立候選字串 要複製 O(L) 個字元，因此固定 26 字母表下，這份實作的期望時間為 O(NL²)，字元儲存為 O(NL)。直接寫成 O(NL) 等於錯把字串建立視為常數操作。
回答前需要釐清的問題
- 回傳值究竟計算什麼？ 本題同時計入兩個端點，所以一次直接合法轉換回傳
2；若介面要求
邊數，結果應少一。
endWord必須在字典中嗎？ 必須。不在時，搜尋前直接回傳0。允許目標不在字典中的
變體會改變這條提前結束規則。
- 單字長度和字母表是否固定？ 是，長度為
L，只含小寫英文字母。Unicode、不同長度或更大
字母表會改變鄰居產生方式與成本。
- 字典元素是否唯一？ 是。仍要轉成集合以取得期望
O(1)的查找和刪除。即使允許重複，
重複字串也不應形成多個頂點。
- 要回傳長度、一條路徑還是所有最短路徑？ 基礎題只要長度。回傳一條路徑需要雙向父指標；
回傳所有最短路徑要保留同一 BFS 層的所有父節點，不能原樣沿用立即刪除規則。
- 字典只查詢一次，還是會服務很多查詢？ 單次查詢適合按需替換字母，不必建立完整索引；
穩定字典上的大量查詢可能值得共用萬用字元模式索引。
beginWord可能已經在字典中嗎？ 可以。它仍是一個頂點，初始化時應從未造訪集合移除。
30 秒回答架構
「我會把每個單字視為頂點，恰好相差一個位置的兩個單字之間連邊。每條邊代表一次轉換，因此這是 無權最短路徑。我從 beginWord 和 endWord 同時做 BFS，每輪展開較小的完整層前緣。對前緣中 的每個單字，產生最多 25L 個單字母變體，並在雜湊集合中查找。若候選單字位於另一側目前前緣， 兩段最短前綴已經連接，回傳目前單字計數加一；否則，未造訪候選單字一加入下一層就立刻從集合 刪除。endWord 不在字典中或任一前緣耗盡時回傳零。最壞仍會造訪 N 個單字；Python 建立每個 候選單字需要複製 L 個字元，所以時間是 O(NL²)，字元儲存是 O(NL)。我會測試直接轉換、 無法抵達、循環、多父節點重複發現，以及兩側前緣大小懸殊的情況。」
分步深入解答
先建立圖模型。頂點集合包含全部字典單字和 beginWord。任意兩個等長單字的漢明距離為一時 連邊。這張圖是無向圖：hot 能變成 dot，反向也合法；它也是無權圖，因為每次合法修改只 貢獻一條邊。
顯式建圖要逐對比較單字，預處理為 O(N²L)，即使絕大多數單字互不相鄰也要付出成本。輸入的 字母表提供了更小的候選空間：每個單字最多只有 25L 個不同的單字母變體，集合成員判斷再決定 哪些候選是真實頂點。
單向 BFS 已經正確。它維持以下不變量：
在第 k 層開始時：
frontier 恰好包含邊距離為 k 的已發現單字；
不存在距離小於 k 的未發現單字；
所有已離開 unvisited 的單字都已經取得最小距離。BFS 只從第 k 層產生第 k + 1 層，因此某個單字首次被發現時，路徑已經最短。在發現時就從 unvisited 刪除它，既保留這項事實，也避免重複進入前緣。
已知單一目標時，可以從兩端搜尋。front 是起點側的一個完整距離層，back 是終點側的一個 完整距離層。sequence_length 等於兩個目前前緣深度之和再加一，因為它計入兩側前緣單字，卻 還沒有計入連接它們的邊。展開任一側的完整層都會讓深度和增加一。如果產生的候選單字屬於另一側 前緣，連接邊使答案成為 sequence_length + 1。
展開較小前緣只改變效能，不改變正確性。交換兩個集合只是選擇下一步推進哪個合法 BFS 層；兩邊 仍分別代表距各自端點的一個確定深度。相交判斷必須針對另一側目前前緣。使用一個全域 unvisited 是安全的：一側發現單字時會立刻占用它。假如之後另一側的展開邊能跨到已展開的 舊層，舊層當初展開時就會先發現同一個單字，因此兩次搜尋不會在目前前緣背後悄悄交叉。
ALPHABET = "abcdefghijklmnopqrstuvwxyz"
def ladder_length(
begin_word: str,
end_word: str,
word_list: list[str],
) -> int:
unvisited = set(word_list)
if end_word not in unvisited:
return 0
front = {begin_word}
back = {end_word}
unvisited.discard(begin_word)
unvisited.remove(end_word)
sequence_length = 1
while front and back:
if len(front) > len(back):
front, back = back, front
next_front: set[str] = set()
for word in front:
for index, original in enumerate(word):
for letter in ALPHABET:
if letter == original:
continue
candidate = word[:index] + letter + word[index + 1 :]
if candidate in back:
return sequence_length + 1
if candidate in unvisited:
unvisited.remove(candidate)
next_front.add(candidate)
front = next_front
sequence_length += 1
return 0範例的前緣層次如下：
| 展開輪次 | 起點側前緣 | 終點側前緣 | 展開前計數 | |---|---|---|---:| | 1 | hit | cog | 1 | | 2 | hot | cog | 2 | | 3 | dot, lot | cog | 3 | | 4 | dot, lot | dog, log | 4 |
第三輪會改為展開較小的 cog 側。第四輪中，dot 與 dog 或 lot 與 log 相連，因此回傳 5。集合走訪順序可能選到另一條最短相交邊，但長度不變。
令 N 為字典規模，L 為單字長度。每個單字最多進入前緣一次；若被展開，就嘗試 25L 個 候選。雜湊查找期望為 O(1)，但 Python 的切片和串接每次花 O(L)，所以固定字母表下最壞 期望時間為 O(NL²)。集合最多保存 O(N) 個參照，其中字串包含 O(NL) 個字元；臨時候選 單字一次額外占 O(L)。即使用可變字元緩衝，具體化或雜湊候選單字仍要查看 L 個字元，嚴謹 上界不變。
主要替代方案是萬用字元模式索引。把 hot 映射到 ot、ht、ho* 等桶。大量查詢可以 共用索引，也不用嘗試字典從未出現的字母。在 Python 中，替 N 個單字建立 L 個模式同樣 包含 O(NL²) 的字元工作，並保留 O(NL) 個桶項目。BFS 使用過某個模式後要清空對應桶或 記錄已處理，否則很多單字會重複掃描同一個大桶，再次產生平方級工作。目前限制下只有一次查詢， 按需變異加集合更容易實作和證明。
測試要覆蓋可執行契約，不能只跑範例：
cases = [
(
"hit",
"cog",
["hot", "dot", "dog", "lot", "log", "cog"],
5,
),
("hit", "cog", ["hot", "dot", "dog", "lot", "log"], 0),
("a", "c", ["a", "b", "c"], 2),
("red", "tax", ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"], 4),
("aaa", "bbb", ["aab", "abb", "bbb", "aba", "baa"], 4),
]
for begin_word, end_word, words, expected in cases:
actual = ladder_length(begin_word, end_word, words)
assert actual == expected, (begin_word, end_word, actual, expected)屬性測試可以隨機產生小型字典，逐對比較建立顯式圖，以普通 BFS 作為可信對照，再與最佳化函式 比較。還要確認輸入串列不變、覆蓋一側前緣成長遠快於另一側的字典，並驗證經多個父節點可抵達的 單字只會展開一次。
高品質示範回答
「這些單字構成一張隱式無向圖。合法單字是頂點，漢明距離為一時連邊。每條邊成本都是一，所以 BFS 能求出最少轉換次數。本題回傳單字數，因此 hit -> hot 的長度是二。
我先把字典放進集合；如果 endWord 不存在，直接回傳零。接著在兩個端點分別維護一個前緣，並 維護一份兩側都尚未發現的單字集合。每輪展開較小的完整前緣。對每個單字的每個位置，嘗試其餘 25 個小寫字母。先判斷候選單字是否在另一側目前前緣；如果命中，兩段 BFS 最短前綴已經連接， 回傳累計單字數加一。否則，候選單字若尚未造訪，就立刻刪除並加入下一層。
不變量是：兩個前緣分別是距各自端點的一個精確距離層；任何已刪除單字都已取得發現側的最小 距離。展開較小一側不會破壞層次。第一次前緣相連一定最短，因為任何更短路徑都會在更早、深度和 更小的兩層之間產生連接。發現時刪除可以阻止重複加入。
最多展開 N 個單字。每個單字產生 25L 個變體，Python 建立每個候選單字花 O(L)，所以 我會寫期望時間 O(NL²)、字元儲存 O(NL)。雙向搜尋通常減少造訪狀態，但最壞上界不變。 若穩定字典要服務大量查詢，我會考慮共用萬用字元索引；單次查詢用字元替換較簡單。驗證包含官方 範例、目標缺少、直接轉換、多條最短路徑、循環，以及與隨機顯式圖對照實作比較。」
常見錯誤
- 用 DFS 並回傳第一條路徑 → DFS 不按轉換次數走訪路徑 → 所有邊權為一時使用 BFS。
- 逐對比較所有字典單字 → 建圖成本達到
O(N²L)→ **每個展開單字只產生最多25L個
候選鄰居。**
- 離開前緣時才標記已造訪 → 多個父節點可能重複加入同一個單字 → **加入前緣時就從
unvisited 刪除。**
- 先檢查
unvisited，再檢查另一側前緣 → 相交單字已被另一側刪除 → **先檢查另一側目前
前緣。**
- 固定展開名為
front的一側 → 一側可能爆量成長，另一側仍很小 → **交換並展開較小的
完整層前緣。**
- 混淆邊數和單字數 → 範例回傳四而不是五 → 計數從一開始，相交時加入連接單字。
- 聲稱雙向 BFS 改善最壞複雜度 → 對抗字典仍可能揭露幾乎所有單字 → **把分支數效益描述為
常見表現，不作保證。**
- 把 Python 變異成本寫成
O(NL)→ 每個候選單字都會複製或雜湊L個字元 → **說明字串
操作模型，這份實作寫 O(NL²)。**
- 共用萬用字元桶卻不消耗 → 同一個大桶被重複掃描 → 每個模式處理後清空或標記。
- 使用全域已造訪集合，卻只展開半層 → 相交順序與距離計數難以證明 → **每輪推進一個完整
前緣層。**
- 把個人貼文當成已核實的公司真題 → 公開自述不是雇主紀錄 → **
companyName保持空值，
僅用它證明目前存在公開討論。**
追問與應對
追問一：如何回傳一條實際的最短序列？
替兩個方向分別保存父指標。發現候選單字時，記錄產生它的單字。相交後，沿起點側父指標回到 beginWord 並反轉前綴，再沿終點側父指標走向 endWord。實作會交換前緣變數，所以父指標必須 按「起點方向」和「終點方向」保存，不能假設目前 front 永遠來自起點。除了字典字串，父指標 還需要 O(N) 個參照。
追問二：Word Ladder II 要回傳所有最短序列，哪裡要改？
每個單字只存一個父節點並不足夠。普通分層 BFS 通常更容易證明：記錄在最小層抵達同一單字的 所有前驅，並在整層處理完成後，才從全域字典刪除本層新發現的單字。這樣允許同層多個父節點， 同時阻止更長路徑繼續新增父節點。首次抵達 endWord 後仍要完成目前這一層，再於前驅 DAG 上 回溯。輸出數量可能是指數級，複雜度必須包含所有回傳序列的數量和長度。
追問三：什麼時候普通單向 BFS 較合適？
字典很小、只知道一個端點、圖有方向且反向鄰居很難產生，或程式簡單性比縮小前緣更重要時，使用 單向 BFS。它的不變量較少，父指標重建也直接。這份 Python 表示下，它沿用同一鄰居產生器和 O(NL²) 上界。
追問四：什麼時候應建立萬用字元模式桶？
大量查詢共用穩定字典、字母表很大，或列舉每個字母的浪費明顯時建立索引。索引要與字典版本 綁定；beginWord 不在索引中時，每次查詢單獨產生其模式；一次搜尋內每個桶最多使用一次。 代價是預處理時間、桶記憶體和字典變更時的失效處理。
追問五：不同字母修改的成本不同時怎麼辦？
圖變成帶權圖，BFS 層次不再代表最小成本。非負成本使用 Dijkstra，仍按需產生相同的隱式鄰居， 但依累計成本選擇前緣。若有可採納啟發式可以使用 A*；只有把漢明距離乘以「任意剩餘字元修改的 已證明最低成本」時，才能直接保證它可採納。
追問六：字母表是 Unicode，或單字長度不同時怎麼辦？
先定義合法操作。Unicode 碼點和使用者看到的字素叢集不是同一單位；允許插入和刪除後還會出現 跨長度邊。單純列舉替換不再涵蓋整張圖。應依契約選擇編輯距離為一的鄰居索引、Trie，或按長度 與模式分桶，並把正規化規則納入相等性與雜湊。
追問七：面試中如何證明雙向搜尋的停止條件？
替兩個目前前緣分別標出到各自端點的深度。演算法每輪只推進一個完整深度層。展開前， sequence_length 等於兩個前緣深度之和加一。產生邊進入另一側前緣時，這條邊組成的路徑恰有 sequence_length + 1 個單字。若存在更短路徑，它必然包含一條連接深度和更小之兩層的邊； 這兩層已經更早展開並相連，與目前是第一次相交矛盾。
追問八：除了範例，如何驗證最佳化搜尋？
對小型隨機字典，逐對連接漢明距離為一的單字，執行普通 BFS 對照實作，再把結果和雙向 BFS 比較，重複數千組。另加執行期不變量：兩個前緣都不與 unvisited 相交；單字不會被發現兩次； 下一層每個單字都與目前層某個單字只差一個字元。這樣得到的是正確性證據，不只是幾個手選輸出。