首页 > > 程序设计 > C/C++ >

#leetcode刷题之路17-电话号码的字母组合

2019-03-13 23:29:14来源：博客园阅读 ()

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

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

先看下图解释：

这道题肯定用的是递归。

首先我们可以看到，输入了几个数字，最终答案里的每一个小项的长度就是几。（例如：我们输入了2 3，这是两个数字，那么答案中的ad、ae、等都是由两个字符组成）

接着，我们那图中列举的第一种情况来分析，首先在第一层我们取首数字的第一个字母元素a，第一层就是在遍历首数字对应的字母，在第二层我们遍历第二个数字对应的字母。要注意这里遍历结束的条件：第一层结束的条件是首数字对应的字母遍历完了，第二层结束条件是第二个字母遍历完了，而当已经生成了由两个字母组成的字符串时，就把这个串加入最终的结果队列。

由此看见，输入的数字的个数、遍历到数字对应的第几个字母、当前生成的字符串（长度），这些都是影响递归的因素。同时，变量中还应有存放答案项的vector以及存放数字字母对应关系的map。

#include <iostream>
#include <map>
#include <vector>
using namespace std;

void combine(string digits,int seq,string current,vector<string> &ans,map<char ,string>num_letters)
{
    if(digits.size()==seq) ans.push_back(current);
    else
    {
        for(int i=0;i<num_letters[digits[seq]].size();i++)//每一层的遍历
        {
            combine(digits,seq+1,current+num_letters[digits[seq]][i],ans,num_letters);
        }
    }
}
vector<string> letterCombinations(string digits) {
    vector<string> ans;
    map<char,string> num_letters;
    if(digits=="") return ans;
    num_letters['2']="abc";
    num_letters['3']="def";
    num_letters['4']="ghi";
    num_letters['5']="jkl";
    num_letters['6']="mno";
    num_letters['7']="pqrs";
    num_letters['8']="tuv";
    num_letters['9']="wxyz";
    combine(digits,0,"",ans,num_letters);
    return ans;
}

int main() {
    string digits="23";
    vector<string> ans=letterCombinations(digits);
    cout<<ans.size()<<endl;
    return 0;
}