每日随机一题.1 电脑版发表于:2021/11/29 22:36 ###电话号码的字母组合(中等) ##### 给定一个仅包含数字2-9的字符串,返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下(与电话按键相同)。注意1不对应任何字母。 ![](https://img.tnblog.net/arcimg/15327697756/8664fb9e1d2c4a42b04850c9e1ddce88.png) ###### 示例 1: 输入:ppx = "2,3" 输出:["ad","ae","af","bd","be","bf","cd","ce","cf"] ###### 示例 2: 输入:ppx = "" 输出:[] ###### 示例 3: 输入:ppx = "9" 输出:["w","x","y","z"] ### 思路 先看第一个数字, 然后把第一个数字对应的字母后面每一个都添加上后一个数字对应的每一个字母, 循环添加,直到最后一个。 我们创建连个列表 第一个列表里面存储上一个数字的所有字符串 第二个列表用于存储对于第一个列表里的字符串添加所有当前数字对应字符的每一个字母 添加完毕之后将第一个列表清空, 将第二个列表里的元素添加到第一个列表中, 然后清空第二个列表。 ```csharp public IList<string> LetterCombinations(string ppx) { List<string> one = new List<string>(); List<string> two = new List<string>(); string val = ""; int length = ppx.Length; if (length == 0) { return one; } Dictionary<char, string> dict = new Dictionary<char, string>(); //存储数字和字符串的对应关系 dict.Add('2', "abc"); dict.Add('3', "def"); dict.Add('4', "ghi"); dict.Add('5', "jkl"); dict.Add('6', "mno"); dict.Add('7', "pqrs"); dict.Add('8', "tuv"); dict.Add('9', "wxyz"); dict.TryGetValue(ppx[0], out val); for (int i = 0; i < val.Length; i++) //这一步是对one进行初始化 { one.Add(val[i].ToString()); } for (int i = 1; i <= length - 1; i++) //循环添加 { val = ""; dict.TryGetValue(ppx[i], out val); foreach (string son in one) { for (int j = 0; j < val.Length; j++) { two.Add(son + val[j]); } } one.Clear(); one.AddRange(two); two.Clear(); } return one; } ``` ~~### 解析 题目为组合题,使用回溯算法 ( 回溯法思路的简单描述是:把问题的解空间转化成了图或者树的结构表示,然后使用深度优先搜索策略进行遍历,遍历的过程中记录和寻找所有可行解或者最优解。)~~