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

L56.【LeetCode题解】电话号码的字母组合

news 2025/6/4 12:35:36

1.17. 电话号码的字母组合

2.分析

举例

枚举算法:使用递归(dfs)

递推

回归

特殊情况的考虑

代码

提交结果

事后回顾: 递归调用的部分展开图

1.17. 电话号码的字母组合

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

2.分析

重点掌握字母排列算法

读题可知:

2对应a、b、c

3对应d、e、f

4对应g、h、i

5对应j、k、l

6对应m、n、o

7对应p、q、r、s

8对应t、u、v

9对应w、x、y、z

举例

考查排列组合,以"258"为例:

2、5和8都有3种选择,可画图:

分类枚举:

再到b和c...... 一共3*3*3==27种情况

枚举算法:使用递归(dfs)

先递推到最底部,枚举完所有情况,再回归到上层,循环前面的过程

使用level表示递归的层数,显然上面举的例子有三层递归,从level==0开始递归,到level==digit.size()才返回

核心:递推时组合字符串,回归时返回字符串(尾插到vector<string> ret中)

递推

设table数组存储数字映射的字符串,vector<string>& ret存储返回的结果

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

向下递推时要组合字符,形成字符串combine_str,但组合的字符从哪里来?

设处在第level层,由于level从0开始计数,因此先找到digits的第level个字符,再将字符转成数字,用变量num存储

size_t num=digits[level]-'0';

该数字对应的字符串是table[num]

由于要枚举所有可能的情况,因此需要遍历字符串table[num],由于是深度遍历,level没有等于digits.size()时,需要一直深度遍历,因此在设计循环时要这样写:

for (int i=0;i<tmp.size();i++)dfs(ret,combine_str+tmp[i],level+1,digits);

注:合并的字符串combine_str不能传引用调用,回归时还要使用,因此是拷贝构造;且level+1不能写成level++,因为回归时还要使用原来的level的值

回归

当level==digits.size()时,回归:先尾插字符串到ret,再return

if (level==digits.size())
{ret.push_back(combine_str);return;
}

显然回归的判断应该写在递归前面

特殊情况的考虑

如果digits为空字符串,需不需要做特殊判断?

假设不用做特殊判断,直接进入dfs函数,那么第一次调用dfs函数时,level==digits.size()==0,ret被尾插空字符串,dfs返回,最终结果: vector不为空,只有一个元素,为空字符串,但这样做显然违背题意

1.空串的含义是有结果的，只不过结果是空串

2.空vector指的是:给定的digits字符串无法得到结果

因此应该返回空的vector

if (digits=="")//注意考虑特殊情况return {};

代码

    //先打表,table[i]为i键位对应的字符串//table[0]和table[1]空出,为了数字与字符串对应static string table[]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
class Solution {
public:void dfs(vector<string>& ret,string combine_str,int level,string& digits){if (level==digits.size()){ret.push_back(combine_str);return;}size_t num=digits[level]-'0';string tmp=table[num];for (int i=0;i<tmp.size();i++)dfs(ret,combine_str+tmp[i],level+1,digits);}vector<string> letterCombinations(string digits) {if (digits=="")//注意考虑特殊情况return {};vector<string> ret;dfs(ret,"",0,digits);//递归函数return ret;}
};