17. 电话号码的字母组合,看完毫无头绪

力扣原题链接（点我直达）

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入：“23” 输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]. 说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

第一版 借助队列

执行用时 :4 ms, 在所有 C++ 提交中击败了80.09%的用户

内存消耗 :8.9 MB, 在所有 C++ 提交中击败了15.91%的用户

    vector<string> result;//用于输出向量
    map<char, string> m = { {'2',"abc" },{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"} };//映射map哈希表
    int size = digits.size();//输入字符串产长度
    queue<string> que;//新建队列

    //先将第一个元素对应的码表入队
    for (int j = 0; j < m[digits[0]].size(); j++)
    {
        string stemp;
        stemp.push_back(m[digits[0]][j]);
        que.push(stemp);//string入队
    }
    string s;//用于存储队头元素
    for (int i = 1; i < size; i++)
    {
        int length = que.size();//当前队列长度
        while (length--)
        {
            for (int j = 0; j < m[digits[i]].size(); j++)
            {
                s = que.front();
                s = s + m[digits[i]][j];//队头元素加上新元素
                que.push(s);//入队
            }
            que.pop();//队头出队
        }
    }
    while (!que.empty())
    {
        result.push_back(que.front());//队头元素存储至res
        que.pop();//队头出队
    }
    return result;//返回

第二版，稍微节省了一点空间

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 :8.7 MB, 在所有 C++ 提交中击败了37.35%的用户

vector<string> result;//用于输出向量
    map<char, string> m = { {'2',"abc" },{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"} };//映射map哈希表
    unsigned i,j,length,size = digits.size();//输入字符串产长度
    queue<string> que;//新建队列

    //先将第一个元素对应的码表入队
    string stemp;
    for (j = 0; j < m[digits[0]].size(); j++)
    {       
        stemp.push_back(m[digits[0]][j]);
        que.push(stemp);//string入队
        stemp.clear();
    }
    for (i = 1; i < size; i++)
    {
        length = que.size();//当前队列长度
        while (length--)
        {
            for (j = 0; j < m[digits[i]].size(); j++)
            {
                stemp = que.front();
                stemp = stemp + m[digits[i]][j];//队头元素加上新元素
                que.push(stemp);//入队
            }
            que.pop();//队头出队
        }
    }
    while (!que.empty())
    {
        result.push_back(que.front());//队头元素存储至res
        que.pop();//队头出队
    }
    return result;//返回