給定
beginWord、endWord與字典wordList，每次只能改一個字母且改後的字必須在字典中。回傳所有最短轉換序列（127 只問最短長度，本題要列出所有最短路徑本身）。
Example:
Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”] Output: [[“hit”,“hot”,“dot”,“dog”,“cog”],[“hit”,“hot”,“lot”,“log”,“cog”]]
Intuition
TIP
核心思路：BFS 逐層擴張找最短距離，過程中記錄每個字的「前驅」（哪些上一層的字能變成它）；找到終點後，用回溯沿前驅重建所有最短路徑。
- 只用 BFS 會丟失路徑、只用 DFS 會爆炸 → BFS 定層 + 記錄前驅 + DFS 回溯
- 每層處理完才從字典移除整層（避免同層互指、又不擋同層多個前驅）
- 找到
endWord就停止往下層擴張（保證最短） - 從
endWord沿前驅回溯到beginWord，反轉即一條路徑
Approaches
1. BFS Shortest Distance + DFS Rebuild — O(N·L·26) / O(N·L)
- Idea: 先 BFS 算出每個字到
beginWord的最短距離dist，再從 begin DFS、每步只走dist剛好 +1 的鄰居到 end - Time:
O(N·L·26)建距離 + 路徑數 × 長度 - Space:
O(N·L)
class Solution {
fun findLadders(beginWord: String, endWord: String, wordList: List<String>): List<List<String>> {
val dict = wordList.toHashSet()
val res = ArrayList<List<String>>()
if (endWord !in dict) return res
dict.add(beginWord)
val dist = HashMap<String, Int>()
dist[beginWord] = 0
val queue = ArrayDeque<String>()
queue.addLast(beginWord)
while (queue.isNotEmpty()) {
val word = queue.removeFirst()
val d = dist[word]!!
val chars = word.toCharArray()
for (k in chars.indices) {
val orig = chars[k]
for (c in 'a'..'z') {
if (c == orig) continue
chars[k] = c
val nxt = String(chars)
if (nxt in dict && nxt !in dist) { dist[nxt] = d + 1; queue.addLast(nxt) }
}
chars[k] = orig
}
}
if (endWord !in dist) return res
val path = ArrayDeque<String>()
path.addLast(beginWord)
fun dfs(word: String) {
if (word == endWord) { res.add(path.toList()); return }
val d = dist[word]!!
val chars = word.toCharArray()
for (k in chars.indices) {
val orig = chars[k]
for (c in 'a'..'z') {
if (c == orig) continue
chars[k] = c
val nxt = String(chars)
if (dist[nxt] == d + 1) { path.addLast(nxt); dfs(nxt); path.removeLast() }
}
chars[k] = orig
}
}
dfs(beginWord)
return res
}
}⭐ 2. BFS Layered Parents + Backtrack Rebuild — O(N·L·26) / O(N·L)
- Idea: BFS 記錄
parents[word]，再從終點回溯所有路徑 - Time:
O(N·L·26)建圖（N 字數、L 字長）+ 路徑數 × 長度 回溯 - Space:
O(N·L)- 前驅表與佇列
class Solution {
fun findLadders(beginWord: String, endWord: String, wordList: List<String>): List<List<String>> {
val dict = wordList.toHashSet()
val res = ArrayList<List<String>>()
if (endWord !in dict) return res
val parents = HashMap<String, MutableList<String>>() // word ← 上一層能變成它的字
var level = hashSetOf(beginWord)
var found = false
while (level.isNotEmpty() && !found) {
for (w in level) dict.remove(w) // 整層移除，避免回頭、保留同層多前驅
val next = HashSet<String>()
for (word in level) {
val chars = word.toCharArray()
for (k in chars.indices) {
val original = chars[k]
for (c in 'a'..'z') {
if (c == original) continue
chars[k] = c
val cand = String(chars)
if (cand in dict) {
if (cand == endWord) found = true
next.add(cand)
parents.getOrPut(cand) { ArrayList() }.add(word)
}
}
chars[k] = original
}
}
level = next
}
if (found) {
val path = ArrayDeque<String>()
path.addLast(endWord)
backtrack(endWord, beginWord, parents, path, res)
}
return res
}
private fun backtrack(
word: String, begin: String, parents: Map<String, List<String>>,
path: ArrayDeque<String>, res: MutableList<List<String>>,
) {
if (word == begin) {
res.add(path.reversed()) // 從 endWord 回溯到 beginWord，反轉即正向路徑
return
}
for (parent in parents[word] ?: emptyList()) {
path.addLast(parent)
backtrack(parent, begin, parents, path, res)
path.removeLast()
}
}
}🔑 Takeaways
- Pattern: BFS 求最短 + 記前驅 + DFS 回溯重建所有路徑（「列出所有最短路徑」的通用框架）
- Key trick: 「整層一起從字典移除」是正確性關鍵——既擋住回頭，又允許同層多個前驅指向同一字；找到終點即停止擴張保證最短。對照 127（只問長度，純 BFS 計層數）即見「列路徑」的額外工。