class Solution {
public:
    const string letterMap[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
    vector<string> result;
    //输入参：转换后的vector ， 从第几个按键开始循环 ， 已经走的路径
    void backtarcking(vector<int> &digits_i , int startidx , string path)
    {   
      //当路径的长度等于数组的长度，存入结果
        if(path.size() == digits_i.size() )
        {
            result.push_back(path);
            return;
        }
        else
        { 
          //第一次循环，循环数字
            for(int i = startidx ; i < digits_i.size() ; i++)
            {
              //找到输入数字对应的字母表
                string tmp = letterMap[digits_i[i]];
                vector<char> tmp_v(tmp.begin() , tmp.end()) ;
                //第二次循环，循环每一个数字的字母
                for(int j=0 ; j < tmp_v.size() ; j++)
                {
                  //递归回溯，开始循环的数字往后走一个，路径加上已经走的路径
                    backtarcking(digits_i, i+1 , path + tmp_v[j]);
                }
            }
            return;
        }
         return;
    }
    vector<string> letterCombinations(string digits) {
    //输入为空时直接返回
        if(digits.size()==0) return result;
    //字符串转换成vector
        vector<int> digits_i;
        for(auto i:digits) digits_i.push_back( i - '0' );
        string path;
        backtarcking(digits_i , 0 , path);
        return result;
    }
};