当前位置：首页 > news >正文

leetcode 17. 电话号码的字母组合

news 来源：原创 2024/5/19 4:22:07

在这里插入图片描述

先审题，给一个数字字符串，要求返回一个字符串数组，里面包含：所有能表示的字母组合。
举例：数字字符串为：“23”,2对应：“abc”,3对应“def”；那么字母组合有：ad，ae，af，bd，be,bf
,cd,ce,cf。
画图实现：

(1)首先需要完成数字和字母的映射关系
可以用一个字符串数组，完成绝对映射：

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

arr[2]=“abc”;arr[3]=“def”。
(2)以输入“23”为例，画图
在这里插入图片描述

a会和def都组合，形成的“ad”==输入的数字字符的大小，说明这个"ad"就是最终形成的字母组合，然后返回，再和“ae”组合，返回后，再和“af”组合，再返回；走到这里说明已经完成了一趟，接下来是b和def的组合，最后是c和def的组合；这个我们可以用一个for循环控制。

代码实现：

 class Solution {
 public:
 //映射关系
    string arr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
 //递归函数
    void AZ(string digits,size_t n,string comb,vector<string>&str)
    {
       if(n==digits.size())
       {
           str.push_back(comb);
           return;
       }
       string _str=arr[digits[n]-'0'];
       for(size_t i=0;i<_str.size();i++)
       {
           AZ(digits,n+1,comb+_str[i],str);
       }  
    }
    
    vector<string> letterCombinations(string digits)
    {
      //返回的字符串数组
      vector<string> ret_str;
      //如果为数字数组为空，直接返回上面的空数组
      if(digits.empty())
      {
          return ret_str;
      }
      //comb用于存临时形成的字母组合
      string comb;
      //AZ函数
      AZ(digits,0,comb,ret_str);
      return ret_str;
    }
};

具体实现AZ函数。

void AZ(string digits,size_t n,string comb,vector<string>&str);

(1)参数：digits存的数字字符串，n用于记录递归的深度，comb用于存形成的字母组合，str要存所有形成的字母组合(str是引用传参)。
注意：用digits=“258”举例。

(2)digits=“258”,那么它的递归深度就是3，也就是digits.size()。所以当n==digits.size()时，说明最终字母组合形成，将comb拷贝进str，并返回到上一层。

     if(n==digits.size())
       {
           str.push_back(comb);
           return;
       }

(3)需要一个字符串来存数字对应的字母；

string _str=arr[digits[n]-'0'];

一上来n=0，那么_str=arr[digits[0]-‘0’]=arr[2]=“abc”;
(4)实现字母的组合，

       for(size_t i=0;i<_str.size();i++)
       {
           AZ(digits,n+1,comb+_str[i],str);
       }

用for循环控制边界，注意是i<_str.size(),往下递归深度要加1，comb要加一个字母。
(5)画图理解AZ()。
在这里插入图片描述

在这里插入图片描述

返回上一级，也就是“ak”层，str里面已经有了一个字母组合“akt”。

继续往下走，

所以这次，str里还会加进去一个字母组合“aku”。然后再返回上级，comb+_str[2]=“akv”,也就会再加一个字母组合“akv”，然后再返回，因为上一层的for循环走完了，所以再返回它的上一级。也就是a层，再组成”aj“往下递归。
在这里插入图片描述
对，画到这里，想必大家已经明白了。