class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits=="") return vector<string>();
        //用数组存储号码键对应的字符串,下标代表号码键的数字
        string res[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        vector<string> arr;
        digui("",digits,res,0,arr);
        return arr;
    }

    void digui(string key,string digits,string res[10],int index,vector<string>& arr){
        int k = digits[index]-'0';//获取输入字符串内部的字符,记得转一下类型
        if(key.size()==digits.size()){
            arr.push_back(key);
            return;
        }
        for(int i=0;i<res[k].size();++i){
            //递归+回溯
            key.push_back(res[k][i]);
            digui(key,digits,res,index+1,arr);
            key.pop_back();
        }
    }
};