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

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

新老客户大回馈,云服务器低至5折

给定一个仅包含数字 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;
}

 


原文链接:https://www.cnblogs.com/biat/p/10517841.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:012章 绪论+向量

下一篇:『ACM C++』 PTA 天梯赛练习集L1 | 027-028