WEI-CHENG CHEN

說明

解法：Backtracking

他的解題想法，有點像是

• 先從 digits 取出當前進度的數字
• 藉由 map，轉成對應的那些英文字母
• 對應的那些英文字母去跑 for 迴圈
  • 先放進去
  • 遞迴
  • 再跑出來

class Solution {
public:
    unordered_map<char, string> m = {
        {'2', "abc"}, {'3', "def"}, {'4', "ghi"},
        {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"},
        {'8', "tuv"}, {'9', "wxyz"},
    };

    void backtrack(vector<string> &ans, string digits, string &current, int index){
        // 終止條件：當遍歷完整個數字字串時，
        if(index == digits.size()){
            ans.push_back(current);
            return;
        }

        // 取得當前數字對應的字母
        string temp_string = m[digits[index]];
        for(char c:temp_string){
            current.push_back(c); // 放進去
            backtrack(ans, digits, current, index+1); // 遞迴
            current.pop_back(); // 拔出來
        }
    }

    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {}; // 避免空輸入導致問題
        vector<string> ans;
        string current;
        backtrack(ans, digits, current, 0);
        return ans;
    }
};