題目描述
給定一個包含 2 到 9 之間數字的字串，傳回該數字可以表示的所有可能的字母組合。以任意順序回傳答案。
下圖為數字對字母的映射（就像電話按鈕一樣）。請注意數字 1 不映射到任何字母。
- 範例 1：
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"] - 範例 2：
Input: digits = ""
Output: [] - 範例 3：
Input: digits = "2"
Output: ["a","b","c"]
解題思路
- 利用回溯法來生成所有可能的字母組合。
- 將數字對應到字母，類似於多層迴圈。
- 特殊情況處理：若輸入字串為空，直接返回空陣列。
解法 1：回溯法
思路
- 每個數字對應的字母表現為樹的不同層次。
- 我們從數字字串的第一個數字開始，逐步選擇其對應的字母，並繼續對下一個數字執行同樣的操作，直到遍歷完整個字串。
- 每當我們生成一個完整的字母組合時，將其加入結果列表中。
詳細步驟
- 定義數字到字母的對應關係，使用字典進行映射。
- 檢查輸入字串是否為空，若空直接返回空列表。
- 使用回溯法逐步生成字母組合：
- 如果當前深度等於輸入字串長度，將組合加入結果。
- 遍歷當前數字對應的所有字母，遞歸地處理下一個數字。
實現 (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）儲存部分結果，逐步處理每個數字。
- 每次處理一個數字時，將隊列中已有的組合與當前數字對應的字母進行拼接。
詳細步驟
- 初始化隊列為空，將第一個數字的所有字母加入隊列。
- 遍歷剩下的數字，對每個數字對應的字母與隊列中現有的組合進行拼接。
- 返回最終的隊列內容。
實現 (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ᵐ)
- 與回溯法不同，這裡需要儲存所有的組合結果，佔用額外的空間。
總結
這題適合初學者熟悉回溯法的核心概念與應用，也可以幫助理解如何用迭代法替代遞歸方法來解決問題。
