17. Letter Combinations of a Phone Number

📘 題目敘述

給定一個只包含數字 2-9 的字串 digits，請回傳所有可能的字母組合（依電話按鍵對應）。

數字與字母對應如下：

2：abc
3：def
4：ghi
5：jkl
6：mno
7：pqrs
8：tuv
9：wxyz

回傳答案可以是任意順序。

條件限制

1 ≤ digits.length ≤ 4
digits[i] 只會是 2 到 9

🧠 解題思路

我這題沒有用遞迴 backtracking，而是把它想成「多進位制枚舉」。

概念是：

每一個 digit 對應一個字母集合（例如 2 -> abc 有 3 個選擇）
如果 digits 長度是 n，那我就要做 n 個位置的組合
我用一個陣列 comb 來記錄「每個位置目前選到第幾個字母」
例如 comb = [0, 1, 2] 表示：
- 第 0 位選第 0 個字母
- 第 1 位選第 1 個字母
- 第 2 位選第 2 個字母

每生成一組字串後，我就讓 comb 像「進位」一樣往前推：

先 comb[n-1]++
如果某一位超出該 digit 的字母數量，就把它歸零並讓前一位 +1

最後用 comb[0] 是否爆掉（超出第一位可選範圍）來當作停止條件。

所有變數

digit：把 digits 字元轉成整數後的陣列，例如 '2' -> 2
n：digits 的長度（幾個數字就代表幾個位置要選字母）
eng：電話按鍵的對照表，eng[x] 是數字 x 對應的字母列表
comb：核心！用來記錄每一個位置目前選到 eng[digit[i]] 的第幾個字母（索引）
letter：最後要回傳的所有組合結果
s：每一輪用 comb 組出的一個字串

🪜 主要流程步驟

1. 先把 digits 轉成整數陣列 digit

因為 digits[i] 是字元，我先做：
- digit.push_back(digits[i] - '0')
這樣後面查表 eng[digit[j]] 才方便

2. 建立電話按鍵對照表 eng

我用 vector<vector<char>> eng 存：
- eng[2] = {'a','b','c'}
- eng[3] = {'d','e','f'}
- ...
0、1 沒有對應字母，所以放空 {}

3. 用 comb 當「多進位制計數器」枚舉所有組合

初始化

comb 長度是 n，一開始全部是 0
表示每一位都先選第一個字母

while 條件：看第一位有沒有爆掉

我用：
- while (comb[0] < eng[digit[0]].size())
意思是：只要第一位的選擇索引還合法，就代表還有組合沒列完
只看第一個位置會爆的地方：因為後面每一位都會進位回到前面，最後一定是第一位先超出範圍，整個枚舉才結束

4. 每一輪：用 comb 組出一個字串 s

我跑 j = 0..n-1：
第 j 位的字母就是 eng[digit[j]][comb[j]]
把它們串起來就是一個合法組合 s
letter.push_back(s) 存進答案

5. 更新 comb：從最後一位開始進位

我用兩段邏輯完成「進位制」：

第一步：先讓最後一位 +1

comb[n-1]++

第二步：處理進位（從右往左）

如果 comb[k] >= eng[digit[k]].size()，代表第 k 位爆掉了：
comb[k] = 0（歸零）
comb[k-1]++（進位到前一位）

這就跟「十進位」的 999 + 1 變 1000 一樣，只是每一位的基底不同（3 或 4）。

💻 程式碼實作

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<int> digit;
        int n = digits.size();
        for (int i = 0; i < n; i++) {
            digit.push_back((int)digits[i] - (int)'0');
        }
        vector<string> letter;
        vector<vector<char>> eng = {{},
                                    {},
                                    {'a', 'b', 'c'},
                                    {'d', 'e', 'f'},
                                    {'g', 'h', 'i'},
                                    {'j', 'k', 'l'},
                                    {'m', 'n', 'o'},
                                    {'p', 'q', 'r', 's'},
                                    {'t', 'u', 'v'},
                                    {'w', 'x', 'y', 'z'}};
        vector<int> comb(n, 0);
        while (comb[0] < eng[digit[0]].size()) {
            string s = "";
            for (int j = 0; j < n; j++) {
                s = s + eng[digit[j]][comb[j]];
            }
            letter.push_back(s);
            comb[n - 1]++;
            for (int k = n - 1; k > 0; k--) {
                if (comb[k] >= eng[digit[k]].size()) {
                    comb[k] = 0;
                    comb[k - 1]++;
                }
            }
        }
        return letter;
    }
};

🔗 題目連結

https://leetcode.com/problems/letter-combinations-of-a-phone-number/