一、题目
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写法即可：
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)
三、总结
回溯算法，可以用来寻找所有的可行解。
在题目中出现找出所有组合的字样的时候，就要想到是否可以用回溯算法。
在使用回溯算法的时候如果发现一个解不可行，则会舍弃不可行的解。
在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。
