【LeetCode】17. 電話號碼的字母組合

文章目錄

17. 電話號碼的字母組合
- 題目描述
- 示例 1：
- 示例 2：
- 示例 3：
- 提示：
- 解題思路
- - 算法分析
  - 問題本質分析
  - 回溯法詳解
  - 組合生成過程可視化
  - 數字映射關系
  - 各種解法對比
  - 算法流程圖
  - 邊界情況處理
  - 時間復雜度分析
  - 空間復雜度分析
  - 關鍵優化點
  - 實際應用場景
  - 測試用例設計
  - 代碼實現要點
- 完整題解代碼

17. 電話號碼的字母組合

題目描述

給定一個僅包含數字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按任意順序返回。

給出數字到字母的映射如下（與電話按鍵相同）。注意 1 不對應任何字母。

在這里插入圖片描述

示例 1：

輸入：digits = “23”
輸出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2：

輸入：digits = “”
輸出：[]

示例 3：

輸入：digits = “2”
輸出：[“a”,“b”,“c”]

提示：

0 <= digits.length <= 4
digits[i] 是范圍 [‘2’, ‘9’] 的一個數字。

解題思路

這道題要求根據電話號碼的數字組合，生成所有可能的字母組合。這是一個經典的回溯算法問題，需要枚舉所有可能的組合。每個數字對應3-4個字母，需要生成所有可能的排列組合。

算法分析

這道題的核心思想是回溯枚舉，主要解法包括：

回溯法：使用遞歸和回溯生成所有組合（推薦）
迭代法：使用隊列進行層序遍歷
優化版本：使用strings.Builder提高字符串操作效率
BFS方法：廣度優先搜索生成組合
遞歸分治：使用分治思想逐步構建組合

問題本質分析

graph TDA[電話號碼字母組合] --> B[數字映射]B --> C[組合生成]C --> D[回溯枚舉]B --> E[2→abc, 3→def, 4→ghi]B --> F[5→jkl, 6→mno, 7→pqrs]B --> G[8→tuv, 9→wxyz]C --> H[每個位置選擇字母]C --> I[生成所有可能組合]D --> J[遞歸回溯]E --> K[映射關系建立]F --> KG --> KH --> L[組合策略]I --> LJ --> L

回溯法詳解

flowchart TDA[輸入digits字符串] --> B{digits為空?}B -->|是| C[返回空數組]B -->|否| D[初始化結果數組]D --> E[調用回溯函數backtrack]E --> F[backtrack(index=0, current="")]F --> G{index == len(digits)?}G -->|是| H[添加current到結果]G -->|否| I[獲取當前數字對應的字母]H --> J[返回結果]I --> K[遍歷每個字母]K --> L[選擇當前字母]L --> M[遞歸調用backtrack(index+1)]M --> N[回溯：移除當前字母]N --> O{還有字母?}O -->|是| KO -->|否| P[返回上一層]G --> Q[終止條件處理]Q --> R[結果收集]

組合生成過程可視化

數字映射關系

graph TDA[數字映射表] --> B[2 → abc]A --> C[3 → def]A --> D[4 → ghi]A --> E[5 → jkl]A --> F[6 → mno]A --> G[7 → pqrs]A --> H[8 → tuv]A --> I[9 → wxyz]B --> J[3個字母]C --> JD --> JE --> JF --> JG --> K[4個字母]H --> JI --> KJ --> L[標準按鍵]K --> M[擴展按鍵]L --> N[組合數量計算]M --> N

各種解法對比

算法流程圖

flowchart TDA[開始] --> B{digits為空?}B -->|是| C[返回空數組]B -->|否| D[初始化結果數組]D --> E[調用backtrack(0, '')]E --> F{index >= len(digits)?}F -->|是| G[添加current到結果]F -->|否| H[獲取當前數字的字母]G --> I[返回結果]H --> J[遍歷每個字母]J --> K[選擇當前字母]K --> L[遞歸backtrack(index+1)]L --> M[回溯：移除字母]M --> N{還有字母?}N -->|是| JN -->|否| O[返回]F --> P[遞歸終止條件]P --> Q[結果收集和返回]

邊界情況處理

時間復雜度分析

空間復雜度分析

關鍵優化點

實際應用場景

測試用例設計

代碼實現要點

回溯策略：
- 使用遞歸函數進行深度優先搜索
- 在每個位置嘗試所有可能的字母
- 到達葉子節點時收集結果
狀態管理：
- 維護當前構建的字符串
- 記錄當前處理的位置
- 正確進行回溯操作
映射關系：
- 建立數字到字母的映射表
- 處理7和9的4個字母情況
- 使用數組或map存儲映射
邊界處理：
- 空字符串返回空數組
- 單個數字直接返回對應字母
- 確保所有情況都有正確輸出
性能優化：
- 使用strings.Builder減少字符串拼接開銷
- 避免不必要的內存分配
- 選擇合適的遞歸深度

這個問題的關鍵在于理解回溯算法的核心思想和掌握遞歸狀態管理，通過深度優先搜索枚舉所有可能的字母組合。特別是回溯操作，需要在每次遞歸調用后正確恢復狀態，確保能夠嘗試所有可能的組合。時間復雜度為O(4^n)，其中n是digits的長度，因為每個數字最多對應4個字母。

完整題解代碼

package mainimport ("fmt""strings"
)// letterCombinations 電話號碼的字母組合 - 回溯法
// 時間復雜度: O(4^n)，其中n是digits的長度，每個數字最多對應4個字母
// 空間復雜度: O(n)，遞歸調用棧深度
func letterCombinations(digits string) []string {if len(digits) == 0 {return []string{}}// 數字到字母的映射digitMap := map[byte]string{'2': "abc",'3': "def",'4': "ghi",'5': "jkl",'6': "mno",'7': "pqrs",'8': "tuv",'9': "wxyz",}var result []stringvar backtrack func(index int, current string)backtrack = func(index int, current string) {// 如果已經處理完所有數字，添加當前組合到結果if index == len(digits) {result = append(result, current)return}// 獲取當前數字對應的字母letters := digitMap[digits[index]]// 嘗試每個字母for _, letter := range letters {backtrack(index+1, current+string(letter))}}backtrack(0, "")return result
}// letterCombinationsIterative 迭代法 - 使用隊列
// 時間復雜度: O(4^n)
// 空間復雜度: O(4^n)，存儲所有可能的組合
func letterCombinationsIterative(digits string) []string {if len(digits) == 0 {return []string{}}// 數字到字母的映射digitMap := map[byte]string{'2': "abc",'3': "def",'4': "ghi",'5': "jkl",'6': "mno",'7': "pqrs",'8': "tuv",'9': "wxyz",}// 使用隊列存儲當前所有可能的組合queue := []string{""}// 逐個處理每個數字for i := 0; i < len(digits); i++ {letters := digitMap[digits[i]]levelSize := len(queue)// 處理當前層的所有組合for j := 0; j < levelSize; j++ {current := queue[0]queue = queue[1:]// 為當前組合添加每個可能的字母for _, letter := range letters {queue = append(queue, current+string(letter))}}}return queue
}// letterCombinationsOptimized 優化版本 - 使用strings.Builder
// 時間復雜度: O(4^n)
// 空間復雜度: O(n)
func letterCombinationsOptimized(digits string) []string {if len(digits) == 0 {return []string{}}// 使用數組映射，避免map查找開銷digitMap := [][]byte{{}, {}, // 0, 1 不對應字母{'a', 'b', 'c'},      // 2{'d', 'e', 'f'},      // 3{'g', 'h', 'i'},      // 4{'j', 'k', 'l'},      // 5{'m', 'n', 'o'},      // 6{'p', 'q', 'r', 's'}, // 7{'t', 'u', 'v'},      // 8{'w', 'x', 'y', 'z'}, // 9}var result []stringvar backtrack func(index int, current *strings.Builder)backtrack = func(index int, current *strings.Builder) {if index == len(digits) {result = append(result, current.String())return}digit := digits[index] - '0'letters := digitMap[digit]for _, letter := range letters {current.WriteByte(letter)backtrack(index+1, current)// 回溯：移除最后添加的字符currentStr := current.String()current.Reset()current.WriteString(currentStr[:len(currentStr)-1])}}backtrack(0, &strings.Builder{})return result
}// letterCombinationsBFS BFS方法 - 層序遍歷
// 時間復雜度: O(4^n)
// 空間復雜度: O(4^n)
func letterCombinationsBFS(digits string) []string {if len(digits) == 0 {return []string{}}digitMap := map[byte]string{'2': "abc",'3': "def",'4': "ghi",'5': "jkl",'6': "mno",'7': "pqrs",'8': "tuv",'9': "wxyz",}// BFS隊列queue := []string{""}for i := 0; i < len(digits); i++ {letters := digitMap[digits[i]]levelSize := len(queue)// 處理當前層的所有組合for j := 0; j < levelSize; j++ {current := queue[0]queue = queue[1:]// 為當前組合添加每個可能的字母for _, letter := range letters {queue = append(queue, current+string(letter))}}}return queue
}// letterCombinationsRecursive 純遞歸方法 - 分治思想
// 時間復雜度: O(4^n)
// 空間復雜度: O(n)
func letterCombinationsRecursive(digits string) []string {if len(digits) == 0 {return []string{}}if len(digits) == 1 {return getLetters(digits[0])}// 分治：處理第一個數字，遞歸處理剩余數字firstLetters := getLetters(digits[0])remainingCombinations := letterCombinationsRecursive(digits[1:])var result []stringfor _, letter := range firstLetters {for _, combination := range remainingCombinations {result = append(result, string(letter)+combination)}}return result
}// getLetters 獲取單個數字對應的字母
func getLetters(digit byte) []string {switch digit {case '2':return []string{"a", "b", "c"}case '3':return []string{"d", "e", "f"}case '4':return []string{"g", "h", "i"}case '5':return []string{"j", "k", "l"}case '6':return []string{"m", "n", "o"}case '7':return []string{"p", "q", "r", "s"}case '8':return []string{"t", "u", "v"}case '9':return []string{"w", "x", "y", "z"}default:return []string{}}
}func main() {// 測試用例1digits1 := "23"result1 := letterCombinations(digits1)fmt.Printf("示例1: digits = \"%s\"\n", digits1)fmt.Printf("輸出: %v\n", result1)fmt.Printf("期望: [ad ae af bd be bf cd ce cf]\n")fmt.Printf("結果正確: %t\n", len(result1) == 9)fmt.Println()// 測試用例2digits2 := ""result2 := letterCombinations(digits2)fmt.Printf("示例2: digits = \"%s\"\n", digits2)fmt.Printf("輸出: %v\n", result2)fmt.Printf("期望: []\n")fmt.Printf("結果正確: %t\n", len(result2) == 0)fmt.Println()// 測試用例3digits3 := "2"result3 := letterCombinations(digits3)fmt.Printf("示例3: digits = \"%s\"\n", digits3)fmt.Printf("輸出: %v\n", result3)fmt.Printf("期望: [a b c]\n")fmt.Printf("結果正確: %t\n", len(result3) == 3)fmt.Println()// 額外測試用例digits4 := "234"result4 := letterCombinations(digits4)fmt.Printf("額外測試: digits = \"%s\"\n", digits4)fmt.Printf("輸出數量: %d\n", len(result4))fmt.Printf("期望數量: 27 (3×3×3)\n")fmt.Printf("結果正確: %t\n", len(result4) == 27)fmt.Println()// 測試迭代版本fmt.Println("=== 迭代版本測試 ===")result1Iter := letterCombinationsIterative(digits1)result2Iter := letterCombinationsIterative(digits2)fmt.Printf("迭代版本示例1: %v\n", result1Iter)fmt.Printf("迭代版本示例2: %v\n", result2Iter)fmt.Printf("結果一致: %t\n", len(result1Iter) == len(result1) && len(result2Iter) == len(result2))fmt.Println()// 測試優化版本fmt.Println("=== 優化版本測試 ===")result1Opt := letterCombinationsOptimized(digits1)result2Opt := letterCombinationsOptimized(digits2)fmt.Printf("優化版本示例1: %v\n", result1Opt)fmt.Printf("優化版本示例2: %v\n", result2Opt)fmt.Printf("結果一致: %t\n", len(result1Opt) == len(result1) && len(result2Opt) == len(result2))fmt.Println()// 測試BFS版本fmt.Println("=== BFS版本測試 ===")result1BFS := letterCombinationsBFS(digits1)result2BFS := letterCombinationsBFS(digits2)fmt.Printf("BFS版本示例1: %v\n", result1BFS)fmt.Printf("BFS版本示例2: %v\n", result2BFS)fmt.Printf("結果一致: %t\n", len(result1BFS) == len(result1) && len(result2BFS) == len(result2))fmt.Println()// 測試遞歸版本fmt.Println("=== 遞歸版本測試 ===")result1Rec := letterCombinationsRecursive(digits1)result2Rec := letterCombinationsRecursive(digits2)fmt.Printf("遞歸版本示例1: %v\n", result1Rec)fmt.Printf("遞歸版本示例2: %v\n", result2Rec)fmt.Printf("結果一致: %t\n", len(result1Rec) == len(result1) && len(result2Rec) == len(result2))fmt.Println()// 邊界值測試fmt.Println("=== 邊界值測試 ===")boundaryTests := []string{"",     // 空字符串"2",    // 單個數字"99",   // 兩個相同數字"2345", // 四個不同數字"7777", // 四個相同數字}for _, test := range boundaryTests {result := letterCombinations(test)expectedCount := 1for _, digit := range test {switch digit {case '7', '9':expectedCount *= 4default:expectedCount *= 3}}fmt.Printf("digits = \"%s\", result count = %d, expected = %d\n", test, len(result), expectedCount)}
}