題目描述:給定一個由數字 2-9 組成的字串 digits,回傳所有它可能代表的字母組合。每個數字對應的字母與電話按鍵相同(2→abc、3→def、…、9→wxyz)。若 digits 為空,回傳空陣列。
解題思路:使用深度優先搜尋(DFS)/ 回溯法,每層遞迴對應一個數字位元,負責從該數字映射的字母集合中選取一個字母加入當前路徑。當路徑長度等於 digits 的長度時,表示已為每個數字都選了一個字母,將路徑作為完整組合加入答案。關鍵點:用一個陣列(或 unordered_map)預先建立數字到字母集的映射,遞迴時以 index 追蹤當前處理到第幾個數字,確保每層只枚舉當前數字的字母。
時間複雜度:O(4ⁿ · n) — 最壞情況下每個數字對應 4 個字母(7 和 9),共 n 個數字,組合數最多 4ⁿ;每個組合複製至答案需 O(n),故總時間為 O(4ⁿ · n)。實際上大多數數字只有 3 個字母,平均更接近 O(3ⁿ · n)。
空間複雜度:O(n) — 遞迴堆疊深度等於 digits 長度 n,path 字串長度亦為 n(不計輸出空間)。
1. If digits is empty: return []
2. Build phoneMap: {'2':"abc", '3':"def", ..., '9':"wxyz"}
3. Define backtrack(index, path):
a. If index == len(digits): append path to result; return
b. For each letter c in phoneMap[digits[index]]:
i. Append c to path
ii. Recurse: backtrack(index+1, path)
iii.Remove last character from path
4. Call backtrack(0, "")
5. Return resultBFS 迭代法 O(4ⁿ · n):維護一個佇列,初始放入空字串;對每個數字,從佇列取出所有目前的部分組合,各自附加當前數字的每個字母後再放回佇列。最終佇列中即為所有完整組合。避免了遞迴呼叫堆疊,但當組合數量極大時佇列佔用記憶體更多。
迭代 + 字串串接 O(4ⁿ · n):與 BFS 類似,但使用 vector<string> 直接替換:對每個數字,將現有所有組合乘以當前字母數量展開。程式碼簡潔,但每次展開需重新複製所有字串,常數因子較大。
0(對應空格)和 1(無字母映射)?digits 非常長(例如 n=15),4¹⁵ ≈ 10 億,如何用生成器(lazy evaluation)的方式按需產生下一個組合,而不是一次性列出全部?