电话号码的字母组合 【C++】【力扣刷题】

 解题思路：

• 以第一个为例,digits = “23”，表明从电话号码的按键中选取2和3这两个字符，然后去寻找它们各自所对应的字母，这里每一个数字字符所对应的字母的不同，0对应的是空字符，而1的话题目中讲到是不对应任何字母，要注意的是像7和9所对应的是4个字母。
• 以上这些应该用一个数组或者容器将它们存起来。
• 这里由于digits的个数是不确定的，所以我们没有办法使用多层for循环来嵌套求解。就需要用到递归，回溯的方式来解题。
• 那么不难想象，这题应该是多叉树的递归并且保存数据到vector<string>容器中。

class Solution {
public:  
    vector<string> letterCombinations(string digits)
    {

    }
};

 解题步骤：

        1.看题，传入一个string类的digits对象，里面是字符串.   返回值是vector<string>

所以我们应该创建一个vector<string>容器的对象 vector<string> statistics；

        2.我们需要把对应的关系映射到一维数组中，放到函数外面。

class Solution {
public:
    const char* numStrArr[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" 
    vector<string> letterCombinations(string digits)
    {
        vector<string> statistics;
        //解题过程
        return statistics;
    }
};

    3.我们需要写一个子函数来完成递归操作。那我们需要传什么参数呢? 

        ①我们需要传接收型参数vector<string> statistics;

        ②需要传digits，来获取需要的字符

        ③需要传一个n，来计算深度 

        ④我们还需要能够保存字符串的string类对象

class Solution {
public:
    const char* numStrArr[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
    void _letterCombinations(vector<string>& statistics, string str, int n, string& digits)
    {

    }
    
    vector<string> letterCombinations(string digits)
    {
        vector<string> statistics;
        string str;
        _letterCombinations(statistics, str, 0, digits);
        return statistics;
    }
};

    4. 我们需要写一个递归的返回条件

        当到了最深的层次时，先把字符串push_back到vector的容器中，然后回溯。

  if (n == digits.size())
  {
      statistics.push_back(str);
      Static++;
      return;
  }

5.写执行过程：

int sz = digits[n] - 48;
string s1;
s1 = numStrArr[sz];
for (int i = 0; i < s1.size(); i++)
{
   char ch = s1[i];
   _letterCombinations(statistics, str + ch, n + 1, digits);
}

   过程

        1. sz记录数字，为了通过下标来映射字符串。

        2. 把字符串存储到string类里面，方便访问字符，ch=s1[i]，记录字符

        3. 递归 

   我们为什么是采用+号，而不是+=呢？

        第一遍adg，然后存到vector<string> statistics对象中
        之后退到上一层，str=="ad"，n==2，再递归，把adh存储起来。
        依次进行。

6.还差最后一步：

        有一个测试用例是我们就不能进入子函数。

vector<string> letterCombinations(string digits)
    {
        vector<string> statistics;
        if(digits.size()==0) return statistics;//如果为空，就不进入子函数
        string str;
        _letterCombinations(statistics, str, 0, digits);
        return statistics;
    }

6.完整的代码：

class Solution {
public:
    const char* numStrArr[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
    void _letterCombinations(vector<string>& statistics, string str, int n, string& digits)
    {
        if (n == digits.size())
        {
            statistics.push_back(str);
            return;
        }
        int sz = digits[n] - 48;
        string s1;
        s1 = numStrArr[sz];
        for (int i = 0; i < s1.size(); i++)
        {
            char ch = s1[i];
            _letterCombinations(statistics, str + ch, n + 1, digits);
        }

    }
    
    vector<string> letterCombinations(string digits)
    {
        vector<string> statistics;
        if(digits.size()==0) return statistics;
        string str;
        _letterCombinations(statistics, str, 0, digits);
        return statistics;
    }
};