[LeetCode解題攻略] 17. Letter Combinations of a Phone Number

題目描述

給定一個包含 2 到 9 之間數字的字串，傳回該數字可以表示的所有可能的字母組合。以任意順序回傳答案。

下圖為數字對字母的映射（就像電話按鈕一樣）。請注意數字 1 不映射到任何字母。

1. 範例 1：

   Input: digits = "23"
   Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

2. 範例 2：

   Input: digits = ""
   Output: []

3. 範例 3：

   Input: digits = "2"
   Output: ["a","b","c"]

解題思路

1. 利用回溯法來生成所有可能的字母組合。
2. 將數字對應到字母，類似於多層迴圈。
3. 特殊情況處理：若輸入字串為空，直接返回空陣列。

解法 1：回溯法

思路

• 每個數字對應的字母表現為樹的不同層次。
• 我們從數字字串的第一個數字開始，逐步選擇其對應的字母，並繼續對下一個數字執行同樣的操作，直到遍歷完整個字串。
• 每當我們生成一個完整的字母組合時，將其加入結果列表中。

詳細步驟

1. 定義數字到字母的對應關係，使用字典進行映射。
2. 檢查輸入字串是否為空，若空直接返回空列表。
3. 使用回溯法逐步生成字母組合：
4. • 如果當前深度等於輸入字串長度，將組合加入結果。
   • 遍歷當前數字對應的所有字母，遞歸地處理下一個數字。

實現 (Python)

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # 數字到字母的映射
        phone_map = {
            "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
        }
        
        # 如果輸入為空，返回空列表
        if not digits:
            return []

        # 回溯函數
        def backtrack(index, path):
            # 如果字母組合完成，加入結果
            if index == len(digits):
                combinations.append("".join(path))
                return
            
            # 獲取當前數字對應的字母
            possible_letters = phone_map[digits[index]]
            for letter in possible_letters:
                # 選擇字母，進一步遞歸
                path.append(letter)
                backtrack(index + 1, path)
                # 回溯：移除剛剛加入的字母
                path.pop()
        
        # 結果列表
        combinations = []
        backtrack(0, [])
        return combinations

時間與空間複雜度

• 時間複雜度：O(3ⁿ × 4ᵐ)
• • 其中 n 是對應於數字 2, 3, 4, 5, 6, 8（每個數字對應 3 個字母）的數量，m 是對應於數字 7, 9（每個數字對應 4 個字母）的數量。
  • 最壞情況下，每個數字都對應 4 個字母，總共有 4^k 種組合，k 是輸入字串的長度。
• 空間複雜度：O(k)
• • 主要來自於遞歸調用堆疊和暫存的路徑 path，k 是輸入字串的長度。

解法 2：迭代法

思路

• 將字母組合問題轉換為多層嵌套的迴圈。
• 使用隊列（Queue）儲存部分結果，逐步處理每個數字。
• 每次處理一個數字時，將隊列中已有的組合與當前數字對應的字母進行拼接。

詳細步驟

1. 初始化隊列為空，將第一個數字的所有字母加入隊列。
2. 遍歷剩下的數字，對每個數字對應的字母與隊列中現有的組合進行拼接。
3. 返回最終的隊列內容。

實現 (Python)

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # 數字到字母的映射
        phone_map = {
            "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
        }
        
        # 如果輸入為空，返回空列表
        if not digits:
            return []

        # 初始化隊列
        queue = deque([""])
        
        for digit in digits:
            for _ in range(len(queue)):
                combination = queue.popleft()
                for letter in phone_map[digit]:
                    queue.append(combination + letter)
        
        return list(queue)

時間與空間複雜度

• 時間複雜度：O(3ⁿ × 4ᵐ)
• • 與回溯法相同，每個數字都可能對應多個字母，所有組合的生成時間是指數級的。
• 空間複雜度：O(3ⁿ × 4ᵐ)
• • 與回溯法不同，這裡需要儲存所有的組合結果，佔用額外的空間。

總結

這題適合初學者熟悉回溯法的核心概念與應用，也可以幫助理解如何用迭代法替代遞歸方法來解決問題。