【華為機試】127. 單詞接龍

文章目錄

127. 單詞接龍
- 描述
- 示例 1：
- 示例 2：
- 提示：
- 解題思路
- - 算法分析
  - 問題本質分析
  - 單向BFS算法詳解
  - 雙向BFS算法詳解
  - 鄰居單詞生成過程
  - 算法流程圖
  - 邊界情況分析
  - 各種解法對比
  - 時間復雜度分析
  - 空間復雜度分析
  - 關鍵優化點
  - 實際應用場景
  - 圖構建策略
  - 雙向BFS優化細節
  - 測試用例設計
  - 算法擴展
  - 代碼實現要點
  - 手工驗證示例
- 完整題解代碼

127. 單詞接龍

描述

字典 wordList 中從單詞 beginWord 到 endWord 的轉換序列是一個按下述規格形成的序列 beginWord -> s1 -> s2 -> … -> sk：

每一對相鄰的單詞只差一個字母。
對于 1 <= i <= k 時，每個 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord
給你兩個單詞 beginWord 和 endWord 和一個字典 wordList ，返回從 beginWord 到 endWord 的最短轉換序列中的單詞數目。如果不存在這樣的轉換序列，返回 0 。

示例 1：

輸入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
輸出：5
解釋：一個最短轉換序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的長度 5。

示例 2：

輸入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
輸出：0
解釋：endWord “cog” 不在字典中，所以無法進行轉換。

提示：

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小寫英文字母組成
beginWord != endWord
wordList 中的所有字符串互不相同

解題思路

算法分析

這道題是圖的最短路徑和BFS廣度優先搜索的經典應用。主要解法包括：

單向BFS：從起點開始廣度優先搜索
雙向BFS：從起點和終點同時搜索
A*搜索：啟發式搜索算法
Dijkstra算法：適用于加權圖的最短路徑

問題本質分析

graph TDA[單詞接龍] --> B[圖的最短路徑問題]B --> C[單向BFS]B --> D[雙向BFS]B --> E[A*搜索]C --> F[從起點層層擴展]D --> G[兩端同時搜索]E --> H[啟發式函數引導]F --> I[時間復雜度O_N2×M]G --> J[時間復雜度O_N×M]H --> K[時間復雜度優化]

單向BFS算法詳解

雙向BFS算法詳解

flowchart TDA[雙向BFS初始化] --> B[創建正向和反向搜索集合]B --> C[beginSet = {beginWord}]C --> D[endSet = {endWord}]D --> E[visited = 空集合]E --> F{beginSet和endSet都非空?}F -->|否| G[返回0]F -->|是| H{beginSet與endSet有交集?}H -->|是| I[返回當前層數]H -->|否| J[選擇較小的集合擴展]J --> K[遍歷當前集合中的每個單詞]K --> L[生成所有可能的鄰居]L --> M{鄰居在對方集合中?}M -->|是| N[找到連接路徑]M -->|否| O{鄰居未被訪問?}O -->|是| P[加入下一層集合]O -->|否| Q[跳過此鄰居]P --> R[標記為已訪問]Q --> LR --> LL --> S{當前單詞所有鄰居處理完?}S -->|否| LS -->|是| T{當前集合所有單詞處理完?}T -->|否| KT -->|是| U[更新當前集合為下一層]U --> V[層數+1]V --> FN --> W[返回總層數]

鄰居單詞生成過程

算法流程圖

邊界情況分析

各種解法對比

graph TDA[解法對比] --> B[單向BFS]A --> C[雙向BFS]A --> D[A*搜索]A --> E[DFS回溯]B --> F[時間O_N2×M空間O_N×M]C --> G[時間O_N×M空間O_N×M]D --> H[時間優化空間O_N×M]E --> I[時間指數級空間O_深度]F --> J[簡單直觀推薦]G --> K[性能最優推薦]H --> L[復雜實現適合研究]I --> M[不適合此問題]

時間復雜度分析

單向BFS：O(N2 × M)，N為單詞數，M為單詞長度
雙向BFS：O(N × M)，搜索空間減半
A*搜索：O(N × M × log N)，依賴啟發函數
DFS回溯：O(N!)，指數級時間復雜度

空間復雜度分析

單向BFS：O(N × M)，隊列和訪問集合
雙向BFS：O(N × M)，兩個搜索集合
A*搜索：O(N × M)，優先隊列和訪問記錄
DFS回溯：O(深度 × M)，遞歸棧空間

關鍵優化點

實際應用場景

圖構建策略

雙向BFS優化細節

測試用例設計

算法擴展

代碼實現要點

圖的表示：
- 使用鄰接表或在線生成鄰居
- 字典可以用Set進行快速查找
- 考慮內存和時間的平衡
BFS實現細節：
- 使用隊列進行層次遍歷
- 記錄訪問狀態避免重復
- 正確處理層數計算
雙向BFS優化：
- 始終擴展較小的集合
- 及時檢測兩個搜索的交集
- 合理的終止條件
鄰居生成策略：
- 枚舉每個位置的所有可能字符
- 利用字典進行有效性檢查
- 避免生成已訪問的單詞

手工驗證示例

graph TDA["hit → cog 示例"] --> B[層次0: hit]B --> C[層次1: hot]C --> D[層次2: dot, lot]D --> E[層次3: dog, log]E --> F[層次4: cog]F --> G[路徑長度 = 5]H[雙向BFS] --> I[正向: hit → hot → dot]H --> J[反向: cog ← dog ← dot]I --> K[在dot處相遇]J --> KK --> L[總長度 = 3 + 2 = 5]

這個問題的關鍵在于理解圖的最短路徑本質和掌握BFS層次遍歷技巧，通過合適的搜索策略找到從起始單詞到目標單詞的最短變換序列。

完整題解代碼

package mainimport ("fmt""strings""time"
)// 解法一：單向BFS（經典解法）
// 時間復雜度：O(N2×M)，空間復雜度：O(N×M)
func ladderLength(beginWord string, endWord string, wordList []string) int {// 特殊情況：起點等于終點if beginWord == endWord {return 1}// 將wordList轉換為set以便快速查找wordSet := make(map[string]bool)for _, word := range wordList {wordSet[word] = true}// 如果endWord不在wordList中，無法到達if !wordSet[endWord] {return 0}// BFS隊列和訪問記錄queue := []string{beginWord}visited := make(map[string]bool)visited[beginWord] = truelevel := 1for len(queue) > 0 {size := len(queue)// 處理當前層的所有單詞for i := 0; i < size; i++ {current := queue[i]// 生成所有可能的鄰居單詞neighbors := getNeighbors(current, wordSet)for _, neighbor := range neighbors {if neighbor == endWord {return level + 1}if !visited[neighbor] {visited[neighbor] = truequeue = append(queue, neighbor)}}}// 更新隊列為下一層queue = queue[size:]level++}return 0
}// 生成所有有效的鄰居單詞
func getNeighbors(word string, wordSet map[string]bool) []string {var neighbors []stringchars := []rune(word)for i := 0; i < len(chars); i++ {original := chars[i]// 嘗試26個字母for c := 'a'; c <= 'z'; c++ {if c == original {continue}chars[i] = cnewWord := string(chars)if wordSet[newWord] {neighbors = append(neighbors, newWord)}}chars[i] = original // 恢復原字符}return neighbors
}// 解法二：雙向BFS（優化解法）
// 時間復雜度：O(N×M)，空間復雜度：O(N×M)
func ladderLengthBidirectional(beginWord string, endWord string, wordList []string) int {// 特殊情況：起點等于終點if beginWord == endWord {return 1}wordSet := make(map[string]bool)for _, word := range wordList {wordSet[word] = true}if !wordSet[endWord] {return 0}// 雙向搜索集合beginSet := make(map[string]bool)endSet := make(map[string]bool)beginSet[beginWord] = trueendSet[endWord] = truevisited := make(map[string]bool)level := 1for len(beginSet) > 0 && len(endSet) > 0 {// 優化：始終擴展較小的集合if len(beginSet) > len(endSet) {beginSet, endSet = endSet, beginSet}nextSet := make(map[string]bool)for word := range beginSet {neighbors := getNeighbors(word, wordSet)for _, neighbor := range neighbors {// 如果在對方集合中找到，說明路徑連通if endSet[neighbor] {return level + 1}// 如果未訪問過，加入下一層if !visited[neighbor] {visited[neighbor] = truenextSet[neighbor] = true}}}beginSet = nextSetlevel++}return 0
}// 解法三：使用模式匹配優化的BFS
// 時間復雜度：O(N×M)，空間復雜度：O(N×M)
func ladderLengthPattern(beginWord string, endWord string, wordList []string) int {if beginWord == endWord {return 1}// 構建模式到單詞的映射patterns := make(map[string][]string)for _, word := range wordList {for i := 0; i < len(word); i++ {pattern := word[:i] + "*" + word[i+1:]patterns[pattern] = append(patterns[pattern], word)}}// 也要為beginWord建立模式for i := 0; i < len(beginWord); i++ {pattern := beginWord[:i] + "*" + beginWord[i+1:]patterns[pattern] = append(patterns[pattern], beginWord)}// BFSqueue := []string{beginWord}visited := make(map[string]bool)visited[beginWord] = truelevel := 1for len(queue) > 0 {size := len(queue)for i := 0; i < size; i++ {current := queue[i]// 通過模式找到所有鄰居for j := 0; j < len(current); j++ {pattern := current[:j] + "*" + current[j+1:]for _, neighbor := range patterns[pattern] {if neighbor == endWord {return level + 1}if !visited[neighbor] && neighbor != current {visited[neighbor] = truequeue = append(queue, neighbor)}}}}queue = queue[size:]level++}return 0
}// 解法四：A*搜索算法
// 時間復雜度：O(N×M×log N)，空間復雜度：O(N×M)
func ladderLengthAStar(beginWord string, endWord string, wordList []string) int {wordSet := make(map[string]bool)for _, word := range wordList {wordSet[word] = true}if !wordSet[endWord] {return 0}// 啟發式函數：計算兩個單詞的差異字符數heuristic := func(word1, word2 string) int {diff := 0for i := 0; i < len(word1); i++ {if word1[i] != word2[i] {diff++}}return diff}// 優先隊列節點type Node struct {word stringg    int // 從起點到當前節點的實際距離f    int // g + h（啟發式距離）}// 簡化的優先隊列實現var pq []Node// 添加起始節點start := Node{word: beginWord,g:    0,f:    heuristic(beginWord, endWord),}pq = append(pq, start)visited := make(map[string]int)visited[beginWord] = 0for len(pq) > 0 {// 簡單的優先隊列：找f值最小的節點minIdx := 0for i := 1; i < len(pq); i++ {if pq[i].f < pq[minIdx].f {minIdx = i}}current := pq[minIdx]pq = append(pq[:minIdx], pq[minIdx+1:]...)if current.word == endWord {return current.g + 1}neighbors := getNeighbors(current.word, wordSet)for _, neighbor := range neighbors {newG := current.g + 1if prevG, exists := visited[neighbor]; !exists || newG < prevG {visited[neighbor] = newGnode := Node{word: neighbor,g:    newG,f:    newG + heuristic(neighbor, endWord),}pq = append(pq, node)}}}return 0
}// 解法五：DFS + 記憶化（遞歸回溯）
// 時間復雜度：O(N!)，空間復雜度：O(N×M + 深度)
func ladderLengthDFS(beginWord string, endWord string, wordList []string) int {wordSet := make(map[string]bool)for _, word := range wordList {wordSet[word] = true}if !wordSet[endWord] {return 0}memo := make(map[string]int)visited := make(map[string]bool)var dfs func(word string) intdfs = func(word string) int {if word == endWord {return 1}if val, exists := memo[word]; exists {return val}visited[word] = trueminLen := 0neighbors := getNeighbors(word, wordSet)for _, neighbor := range neighbors {if !visited[neighbor] {length := dfs(neighbor)if length > 0 {if minLen == 0 || length+1 < minLen {minLen = length + 1}}}}visited[word] = falsememo[word] = minLenreturn minLen}return dfs(beginWord)
}// 測試函數
func testLadderLength() {testCases := []struct {beginWord stringendWord   stringwordList  []stringexpected  intdesc      string}{{"hit", "cog",[]string{"hot", "dot", "dog", "lot", "log", "cog"},5, "示例1：標準轉換路徑",},{"hit", "cog",[]string{"hot", "dot", "dog", "lot", "log"},0, "示例2：目標不在字典中",},{"a", "c",[]string{"a", "b", "c"},2, "簡單單字母轉換",},{"hot", "dog",[]string{"hot", "dog", "dot"},3, "兩步轉換",},{"hot", "dog",[]string{"hot", "dog"},0, "無中間路徑",},{"leet", "code",[]string{"lest", "leet", "lose", "code", "lode", "robe", "lost"},6, "復雜路徑",},{"hit", "hit",[]string{"hit"},1, "起點等于終點",},{"qa", "sq",[]string{"si", "go", "se", "cm", "so", "ph", "mt", "db", "mb", "sb", "kr", "ln", "tm", "le", "av", "sm", "ar", "ci", "ca", "br", "ti", "ba", "to", "ra", "fa", "yo", "ow", "sn", "ya", "cr", "po", "fe", "ho", "ma", "re", "or", "rn", "au", "ur", "rh", "sr", "tc", "lt", "lo", "as", "fr", "nb", "yb", "if", "pb", "ge", "th", "pm", "rb", "sh", "co", "ga", "li", "ha", "hz", "no", "bi", "di", "hi", "qa", "pi", "os", "uh", "wm", "an", "me", "mo", "na", "la", "st", "er", "sc", "ne", "mn", "mi", "am", "ex", "pt", "io", "be", "fm", "ta", "tb", "ni", "mr", "pa", "he", "lr", "sq", "ye"},5, "大字典測試",},}fmt.Println("=== 單詞接龍測試 ===")fmt.Println()for i, tc := range testCases {// 測試主要解法result1 := ladderLength(tc.beginWord, tc.endWord, tc.wordList)result2 := ladderLengthBidirectional(tc.beginWord, tc.endWord, tc.wordList)result3 := ladderLengthPattern(tc.beginWord, tc.endWord, tc.wordList)status := "?"if result1 != tc.expected {status = "?"}fmt.Printf("測試 %d: %s\n", i+1, tc.desc)fmt.Printf("輸入: beginWord=\"%s\", endWord=\"%s\"\n", tc.beginWord, tc.endWord)fmt.Printf("字典: %v\n", tc.wordList)fmt.Printf("期望: %d\n", tc.expected)fmt.Printf("單向BFS: %d\n", result1)fmt.Printf("雙向BFS: %d\n", result2)fmt.Printf("模式匹配: %d\n", result3)fmt.Printf("結果: %s\n", status)fmt.Println(strings.Repeat("-", 50))}
}// 性能測試
func benchmarkLadderLength() {fmt.Println()fmt.Println("=== 性能測試 ===")fmt.Println()// 構造測試數據testData := []struct {beginWord stringendWord   stringwordList  []stringdesc      string}{{"hit", "cog",[]string{"hot", "dot", "dog", "lot", "log", "cog"},"小字典測試",},{"qa", "sq",generateLargeWordList(100, 2),"中等字典測試",},{"start", "enddd",generateLargeWordList(500, 5),"大字典測試",},}algorithms := []struct {name stringfn   func(string, string, []string) int}{{"單向BFS", ladderLength},{"雙向BFS", ladderLengthBidirectional},{"模式匹配", ladderLengthPattern},{"A*搜索", ladderLengthAStar},}for _, data := range testData {fmt.Printf("%s (字典大小: %d):\n", data.desc, len(data.wordList))for _, algo := range algorithms {start := time.Now()result := algo.fn(data.beginWord, data.endWord, data.wordList)duration := time.Since(start)fmt.Printf("  %s: 結果=%d, 耗時: %v\n", algo.name, result, duration)}fmt.Println()}
}// 生成大規模測試詞典
func generateLargeWordList(size, wordLen int) []string {words := make([]string, 0, size)// 生成一些相關的單詞base := strings.Repeat("a", wordLen)words = append(words, base)for i := 1; i < size; i++ {word := []rune(base)// 隨機改變1-2個字符changes := 1 + i%2for j := 0; j < changes; j++ {pos := (i + j) % wordLenword[pos] = rune('a' + (i+j)%26)}words = append(words, string(word))}return words
}// 演示BFS搜索過程
func demonstrateBFS() {fmt.Println("\n=== BFS搜索過程演示 ===")beginWord := "hit"endWord := "cog"wordList := []string{"hot", "dot", "dog", "lot", "log", "cog"}fmt.Printf("從 \"%s\" 到 \"%s\" 的轉換過程:\n", beginWord, endWord)fmt.Printf("字典: %v\n\n", wordList)// 演示搜索層次wordSet := make(map[string]bool)for _, word := range wordList {wordSet[word] = true}queue := []string{beginWord}visited := make(map[string]bool)visited[beginWord] = truelevel := 1fmt.Printf("層次 %d: %v\n", level, queue)for len(queue) > 0 && level <= 5 {size := len(queue)nextLevel := []string{}for i := 0; i < size; i++ {current := queue[i]neighbors := getNeighbors(current, wordSet)for _, neighbor := range neighbors {if neighbor == endWord {fmt.Printf("層次 %d: 找到目標 %s！\n", level+1, neighbor)fmt.Printf("路徑長度: %d\n", level+1)return}if !visited[neighbor] {visited[neighbor] = truenextLevel = append(nextLevel, neighbor)}}}if len(nextLevel) > 0 {queue = nextLevellevel++fmt.Printf("層次 %d: %v\n", level, queue)} else {break}}
}// 演示雙向BFS
func demonstrateBidirectionalBFS() {fmt.Println("\n=== 雙向BFS演示 ===")beginWord := "hit"endWord := "cog"wordList := []string{"hot", "dot", "dog", "lot", "log", "cog"}fmt.Printf("雙向搜索從 \"%s\" 和 \"%s\" 同時開始\n", beginWord, endWord)wordSet := make(map[string]bool)for _, word := range wordList {wordSet[word] = true}beginSet := map[string]bool{beginWord: true}endSet := map[string]bool{endWord: true}visited := make(map[string]bool)level := 1fmt.Printf("層次 %d: 正向=%v, 反向=%v\n", level, getKeys(beginSet), getKeys(endSet))for len(beginSet) > 0 && len(endSet) > 0 && level <= 3 {if len(beginSet) > len(endSet) {beginSet, endSet = endSet, beginSetfmt.Println("交換搜索方向")}nextSet := make(map[string]bool)for word := range beginSet {neighbors := getNeighbors(word, wordSet)for _, neighbor := range neighbors {if endSet[neighbor] {fmt.Printf("層次 %d: 在 %s 處相遇！\n", level+1, neighbor)fmt.Printf("總路徑長度: %d\n", level+1)return}if !visited[neighbor] {visited[neighbor] = truenextSet[neighbor] = true}}}beginSet = nextSetlevel++if len(beginSet) > 0 {fmt.Printf("層次 %d: 當前擴展=%v, 對方=%v\n", level, getKeys(beginSet), getKeys(endSet))}}
}// 輔助函數：獲取map的所有鍵
func getKeys(m map[string]bool) []string {keys := make([]string, 0, len(m))for k := range m {keys = append(keys, k)}return keys
}func main() {fmt.Println("127. 單詞接龍 - 多種解法實現")fmt.Println("=====================================")// 基礎功能測試testLadderLength()// 性能對比測試benchmarkLadderLength()// BFS過程演示demonstrateBFS()// 雙向BFS演示demonstrateBidirectionalBFS()// 展示算法特點fmt.Println("\n=== 算法特點分析 ===")fmt.Println("1. 單向BFS：經典解法，層次遍歷，簡單直觀")fmt.Println("2. 雙向BFS：從兩端搜索，搜索空間減半，性能最優")fmt.Println("3. 模式匹配：預處理優化鄰居查找，減少重復計算")fmt.Println("4. A*搜索：啟發式搜索，適合有明確目標的場景")fmt.Println("5. DFS回溯：遞歸實現，但時間復雜度較高")fmt.Println("\n=== 關鍵技巧總結 ===")fmt.Println("? 圖的建模：將單詞看作圖中的節點，差一個字母的單詞相連")fmt.Println("? BFS層次遍歷：保證找到的第一個路徑是最短的")fmt.Println("? 雙向優化：從兩端同時搜索，顯著減少搜索空間")fmt.Println("? 訪問控制：避免重復訪問和環路問題")fmt.Println("? 集合操作：使用Set進行快速查找和去重")
}