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

题目描述

解题思路：

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

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

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

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

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

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

    void combine(string digits,int level,string str,vector& v)
    {
        if(level==digits.size())
        {
            v.push_back(str);
            return;
        }
        int num=digits[level]-'0';
        string s=A[num];
        for(int i=0;isize();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& v){     
        if(level==digits.size()){
            v.push_back(str);
            return;
        }
        int num=digits[level]-'0';
        string s=A[num];
        for(int i=0;isize();i++){
            combine(digits,level+1,str+s[i],v);
        }
    }
    vector letterCombinations(string digits) {
        vector v;
        if(digits=="")//如果是空串，直接返回空的对象v
        {
            return v;
        }
        combine(digits,0,"",v);//从第0层开始，str为空串
        return v;
    }
};