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哈希表
intsize=digits.size();//输入字符串产长度
queue<string>que;//新建队列
//先将第一个元素对应的码表入队
for (intj=0; j<m[digits[0]].size(); j++)
{
stringstemp;
stemp.push_back(m[digits[0]][j]);
que.push(stemp);//string入队
}
strings;//用于存储队头元素
for (inti=1; i<size; i++)
{
intlength=que.size();//当前队列长度
while (length--)
{
for (intj=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();//队头出队
}
returnresult;//返回
第二版，稍微节省了一点空间
执行用时 :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哈希表
unsignedi,j,length,size=digits.size();//输入字符串产长度
queue<string>que;//新建队列
//先将第一个元素对应的码表入队
stringstemp;
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();//队头出队
}
returnresult;//返回
