这是我参与更文挑战的第18天，活动详情查看： 更文挑战
电话号码的字母组合（题号17）
题目
给定一个仅包含数字 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 <= 4digits[i]是范围['2', '9']的一个数字。
链接
解释
这题啊，这题是想复杂了。
感觉在强行无中生有一种更简单的方法，其实一开始的解法就够了，因为不自信，强行写出另外一种解法，结果毫无意义，效率更低了。
这题的解法其实非常简单，首先搞一个对象，记录数字对应的字母。
之后开始循环就完事，没什么难的地方。
具体的放到代码里说吧，笔者想出的另外一种做法就更加复杂了，感觉不太好理解。
自己的答案（三层循环）
首先看看代码?：
var letterCombinations = function(digits) {
var obj = {
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']
}
arr = []
for (const num of digits) {
if (!arr.length) {
arr = obj[num]
} else {
var tmp = []
for (const item of obj[num]) {
for (const item2 of arr) {
tmp.push(`${item2}${item}`)
}
}
arr = tmp
}
}
return arr
};
复制代码这里的除了对象外，额外声明的变量只有一个，这里叫做arr，其实就是最后的结果，叫res也可以的。
首先res是空的，之后开始循环digits中的每个元素，在这个循环内部，首先判断arr是否为空，如果为空，直接讲对应obj的字母数组放进去。
之后开始第二层和第三层循环，这两层循环一层是当前元素所代表的字母数组，一层是arr，循环顺序无所谓，因为是要穷举所有的可能性。
在最里层的循环中，就可以进行字符串的拼接了。更新arr数组即可。
如果还是不好理解，这里举个? -> 234。
首先开始最外层的循环，此时arr为空，所以直接给arr赋值，循环之后arr为：
[ 'a', 'b', 'c' ]
复制代码之后开始第二层循环，拿arr和数字3所代表的字母互相匹配，得到的结果个数为3 * 3，也就是?：
[ 'ad', 'bd', 'cd', 'ae', 'be', 'ce', 'af', 'bf', 'cf' ]
复制代码之后开始第三层循环，拿arr和数字4代表的字母互相匹配，得到的结果个数为9 * 3，也就是?：
[ 'adg',
'bdg',
'cdg',
'aeg',
'beg',
'ceg',
'afg',
'bfg',
'cfg',
'adh',
'bdh',
'cdh',
'aeh',
'beh',
'ceh',
'afh',
'bfh',
'cfh',
'adi',
'bdi',
'cdi',
'aei',
'bei',
'cei',
'afi',
'bfi',
'cfi' ]
复制代码这样就能拿到最后的结果了，整体思路还是比较简单的。
自己的答案（进位）
该方法就有点奇思妙想了，真不知道自己是怎么想到的。
首先假设开始的字符串所代表的字母为000，以234为?的话，最后的可能性就是333，翻译过来，一开始的字母是adg，最后的字母是cfi。
所以假设start变量为所有的可能性，它会从000一直增加到333。
让我们看看234代表的字母数组，应该是?：
[
['a', 'b', 'c'],
['d', 'e', 'f'],
['g', 'h' ,'i'],
]
复制代码000就对应着每一个元素里面数组的index值，也就是?说的adg了，最后一个自然是cfi`了。
那么接下来要做的就是不断更新start数组，每更新一次就往结果里插入一个元素。
注意这里更新的时候要进行进位操作，比方说当前start是002，下一次增加就会变成003，此时已经超出了当前位的最大长度，就需要进行进位操作，操作完成后就变成了010，之后继续操作就好了。
就这样一直进位，就可以找到所有的可能性，?看看代码：
var letterCombinations = function(digits) {
var obj = {
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']
}
res = []
len = digits.length
item = new Array(len)
max = new Array(len)
start = new Array(len)
transArr = new Array(len)
for (let i = 0; i < digits.length; i++) {
max[i] = obj[digits[i]].length - 1
start[i] = 0
transArr[i] = obj[digits[i]]
}
while (start.toString() !== max.toString()) {
for (let i = start.length - 1; i > -1; i--) {
if (start[i] > max[i]) {
start[i] = 0
start[i - 1] = start[i - 1] + 1
}
}
res.push(start.map((item, index) => transArr[index][item]).join(''))
++start[start.length - 1]
}
max.length && res.push(max.map((item, index) => transArr[index][item]).join(''))
return res
};
复制代码整体逻辑就是这样了，由于while的条件限制，会遗漏掉最后一种情空，所以在while完成后需要把max解析推入res数组中。
本来以为这种方法会强一点，但其实并没有，甚至在内存消耗上更大了，因为存储了多组数据原因吧。
更好的方法（递归）
递归的方法和三层循环其实差不多，也是一点点增加排列组合的可能性，代码?：
var letterCombinations = function(digits) {
var obj = {
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']
}
res = []
function dfs(str, i) {
if (i > digits.length - 1) {
// 有了str的判断后就不需要处理digits为空的情况了
str && res.push(str)
return
}
var letters = obj[digits[i]]
for (const letter of letters) {
dfs(`${str}${letter}`, i + 1)
}
}
dfs('', 0)
return res
};
复制代码递归的方法也很简单，递归函数接受两个参数，一个是str，代表着当前自负从，i表示当前的位置。
如果i已经超出了digits的长度，就直接讲当前字符串插入res，结束递归，否则的话循环i代表的字母数组，开始和str进行排列组合，继续递归。
性能上，递归的耗时略差于三成循环，内存消耗差不多。
其他也就是没啥了，不算很难的一题，纯属笔者想多了。
PS：想查看往期文章和题目可以点击下面的链接：
这里是按照日期分类的?
经过有些朋友的提醒，感觉也应该按照题型分类
这里是按照题型分类的?
有兴趣的也可以看看我的个人主页?
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
