今天就來第17題ㄌ

題目

題目翻譯

給定一個只有數字 2 到 9 的字串 digits，如同電話按鈕一樣，每個數字對應到幾個特定英文字母，要求返回所有的組合

解題思路

1. 問題描述：給定一個數字字符串，每個數字代表電話鍵盤上的字母，返回可能的字母組合。

2. 遞迴方案：

   • 使用遞迴來生成所有的組合。
   • 每次從數字字符串中取出一個數字，將其對應的字母加入當前組合，然後處理剩下的數字。
   • 當字符串處理完後，將完整的組合加入結果列表。

3. 初始化字母對應關係：

   • 構建一個列表，其中數字（從 2 到 9）對應到相應的字母。比如數字 2 對應 "abc"，數字 3 對應 "def"。

4. 處理空字符串的特殊情況：

   • 如果輸入的數字字符串是空的，返回空的結果列表。

5. 主函數調用遞迴：

   • 主函數 letterCombinations 將初始化結果列表，然後調用遞迴函數生成所有組合。

6. 結果返回：

   • 當所有組合生成後，返回結果列表。

code

class Solution {
public:
    // 按鍵對應的字母
    vector<string> buttons = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    // 遞迴函數：生成所有可能的字母組合
    void addLetter(const string& digits, int index, string& current, vector<string>& ans) {
        // 如果到達字符串末尾，將當前組合加入答案
        if (index == digits.size()) {
            ans.push_back(current);
            return;
        }

        // 取得當前數字對應的字母
        int num = digits[index] - '2';  // 將數字轉換為對應的按鍵索引
        for (char ch : buttons[num]) {
            current.push_back(ch);  // 添加當前字母
            addLetter(digits, index + 1, current, ans);  // 處理下一個數字
            current.pop_back();  // 回溯，移除當前字母
        }
    }
    
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};  // 處理空輸入情況
        
        vector<string> ans;
        string current;  // 用於存儲當前的字母組合
        addLetter(digits, 0, current, ans);  // 調用遞迴函數
        return ans;
    }
};