17. 电话号码的字母组合（回溯）

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

输入：digits = ""
输出：[]

输入：digits = "2"
输出：["a","b","c"]

result = List()
for(i=0;i<len("abc");i++) {
    tmp = i
    result.add(tmp)
}
return result

result = List()
for(i=0;i<len("abc");i++) {
    for(j=0;j<len("def");j++)
        tmp = i+j
        result.add(tmp)
}
return result

result = List()
for(i=0;i<len("abc");i+=1) {
    for(j=0;j<len("def");j+=1) {
        for(k=0;k<len("ghi");k+=1) {
            tmp = i+j+k
            result.add(tmp)
        }
    }
}
return result

result = List()
for(i=0;i<len("abc");i+=1) {
    for(j=0;j<len("def");j+=1) {
        for(k=0;k<len("ghi");k+=1) {
            for(n=0;n<len("jkl");n+=1)
                tmp = i+j+k+n
                result.add(tmp)
        }
    }
}
return result

class Solution {
public:
    vector<string> alpht = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//字符表
    vector<string> ans;//用于返回最后的结果
 
    vector<string> letterCombinations(string digits)
    {
        if(digits.size() == 0)
            return {}; //c++11的新特性，这里返回空的vector<string>
 
        recursion(digits, {}, 0); //交给子函数去递归处理
        return ans;
    }
 
    void recursion(const string& digits, string tmp, int index)
    {
        if(index == digits.size())//递归结束的条件
        {
            ans.push_back(tmp);//把最后的结果尾插到ans去
            return;
        }
 
        // 依据digits的位数进行迭代，例如digits="23"
        // 第一层迭代为"2"，将遍历对应的字符串"abc"并更新字符串，依次为"a","b","c"
        // 第二层迭代为"3"，将遍历对应的字符串"def"并更新字符串，若上一层迭代为"a"，则添加、更新为"ad", "ae"与"af".
        int pos = digits[index] - '0'; //pos获取digits中的字符位置
        const string& tmpAlpht = alpht[pos]; //tmpAlpht获取pos位置处的字符串,而且建议传引用，避免拷贝构造
        for(int j = 0; j < tmpAlpht.size(); ++j)
        {
            // 进行下一层迭代，注意同一层迭代时不改变s和idx等参数值
            recursion(digits, tmp + tmpAlpht[j], index + 1);
        }
    }
};

class Solution {
public:
    void backtracking(const string& digits, int startindex)
    {
        if(startindex == digits.size())
        {
            result.push_back(tmp);
            return;
        }
 
        string cur = alpha[digits[startindex] - '0']; // 需要
        for(int i = 0; i < cur.size(); ++i)
        {
            tmp += cur[i];
            backtracking(digits, startindex + 1);
            tmp.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0)
            return {};
        backtracking(digits, 0);
        return result;
    }
private:
    vector<string> alpha{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> result;
    string tmp = "";
};

class Solution {
public:
    vector<string> alpht = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> ans;//用于返回最后的结果
 
    vector<string> letterCombinations(string digits)
    {
        if(digits.size() == 0)
            return {}; //c++11的新特性，这里返回空的vector<string>
 
        queue<string> qe;
        
        //先将第一个数字对应的字符串放到qe中去
        string tmp = alpht[digits[0] - '0'];
        string tmpStr;
        for(int i = 0; i < tmp.size(); ++i)
        {
            tmpStr = tmp[i]; //要用一个string类型接收，才不会是将char类型的插入
            qe.push(tmpStr);
        }
 
        //将digits遍历完
        for(int i = 1; i < digits.size(); ++i)
        {
            //先获取下个数字对应的字符串
            string alphtTmp = alpht[digits[i] - '0']; 
 
            string Front = qe.front(); // 队列首位
            while(Front.size() < i + 1) // 队列首位的字符串是否小于遍历digits的子串的长度
            {
                for(int j = 0; j < alphtTmp.size(); ++j)
                {
                    qe.push(Front + alphtTmp[j]);
                }
                qe.pop(); // 删除首位
                Front = qe.front(); // 更新队列首位
            }
        }
 
        while(!qe.empty()) //队列中剩下的就是结果，把他们都尾插到ans后面
        {
            ans.push_back(qe.front());
            qe.pop();
        }
        return ans;
    }
};