☆打卡算法☆LeetCode 17、电话号码的字母组合 算法解析
> 推荐阅读
>
> - CSDN主页
> - GitHub开源地址
>- Unity3D插件分享
> - 简书地址
> - 我的个人博客
> - QQ群：1040082875
大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
## 一、题目
### 1、算法题目
“返回给定仅包含数字2-9的字符串的所有可能的字母组合。”
题目链接：
来源：力扣（LeetCode）
链接：17. 电话号码的字母组合 - 力扣（LeetCode） (leetcode-cn.com)
### 2、题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
```
示例 1：
输入： digits = “23”
输出： [“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
```
```
示例 2：
输入： digits = “2”
输出： [“a”,“b”,“c”]
```
## 二、解题
### 1、思路分析
这道题可以先使用哈希表存储每个数字对应的所有可能的字母，然后找到所有解即可。
每次取一位数字，然后从哈希表中枚举所有可能的字母，并将其中的一个字母插入到已有字母的后面，然后继续处理下一位数字，直到处理完所有数字，得到一个字母数组。
当题目中出现所有组合字样的时候，就要考虑要用回溯法，使用回溯算法找到所有的可行解，发现一个解不行，舍弃不可行的解，穷举所有解即可。
### 2、代码实现
电话号码的组合本质上就是笛卡尔积，使用linq写法即可：
```csharp
public class Solution {
public IList<string> LetterCombinations(string digits) {
IList<string> result = new List<string>();
if (string.IsNullOrEmpty(digits))
{
return result;
}
Dictionary<char, string> phoneDic = new Dictionary<char, string>() {
{‘2’,“abc” },
{‘3’,“def” },
{‘4’,“ghi” },
{‘5’,“jkl” },
{‘6’,“mno” },
{‘7’,“pqrs” },
{‘8’,“tuv” },
{‘9’,“wxyz” },
};
if (digits.Length == 1)
{
string temp = phoneDic[digits[0]];
for (int i = 0; i < temp.Length; i++)
{
result.Add(temp[i].ToString());
}
return result;
}
List<string> temps = new List<string>();
for(int i = 0; i < digits.Length; i++)
{
temps.Add(phoneDic[digits[i]]);
}
var tempResult = from m in temps[0]
from n in temps[1]
select new string("" + m + n);
for(int i = 2; i < temps.Count; i++)
{
string temp = temps[i];
tempResult = from m in tempResult
from n in temp
select new string("" + m + n);
}
result = tempResult.ToList();
return result;
}
}
```
### 3、时间复杂度
时间复杂度 ： O(N)
空间复杂度： O(1)
## 三、总结
回溯算法，可以用来寻找所有的可行解。
在题目中出现找出所有组合的字样的时候，就要想到是否可以用回溯算法。
在使用回溯算法的时候如果发现一个解不可行，则会舍弃不可行的解。
在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。
- 点赞
- 收藏
- 关注作者
评论（0）