[C++]Leetcode17电话号码的字母组合

[C++]Leetcode17电话号码的字母组合

题目描述

解题思路：

这是一个深度优先遍历的题目，涉及到多路递归，下面通过画图和解析来分析这道题。

首先说到的是映射关系，那么我们就可以通过一个字符串数组来表示映射关系（字符串下标访问对应着数字映射到对应的字符串）比如我们输入的是‘2’，那么通过A[2]就可以得到对应的字符串“abc”

string A[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

我们可以将数字对应的字符串进行分层，然后通过递归来实现深度遍历，for循环来实现广度遍历，从而得到对应的组合。最后将排列组合用vector<string>&类型容器存储起来。

这题我们就拿“246”来举例，我们用level来表示层数，将映射出的字符串划分为0 1 2层，先进行深度遍历，一层一层的将单个字符进行拼接(注意这里拼接得到的字符串str不能使用引用，因为深度遍历完一层之后，进行另外一层遍历我们是不希望受到前面遍历的影响的)比如第一次深度遍历得到“agm”，如果是使用引用传参，那么在第一次遍历之后，str就变成了“agm”在后续遍历中不方便操作。

当level达到所给数字字符串的size的时候也就是level==3时，将得到的字符串str加到vector<string> v里边这里的类型得用引用。

    void combine(string digits,int level,string str,vector<string>& v){if(level==digits.size()){v.push_back(str);return;}int num=digits[level]-'0';string s=A[num];for(int i=0;i<s.size();i++){combine(digits,level+1,str+s[i],v);}}

下面通过画图来演示一下递归流程：

完整代码如下：

class Solution {
public:string A[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//与输入的数字字符形成映射关系void combine(string digits,int level,string str,vector<string>& v){     if(level==digits.size()){v.push_back(str);return;}int num=digits[level]-'0';string s=A[num];for(int i=0;i<s.size();i++){combine(digits,level+1,str+s[i],v);}}vector<string> letterCombinations(string digits) {vector<string> v;if(digits=="")//如果是空串，直接返回空的对象v{return v;}combine(digits,0,"",v);//从第0层开始，str为空串return v;}
};