题目描述：

    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

    输入：”23”
    输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

    思路一：回溯法

    每一个数字映射多个字母，每个字母要和剩余数字的每个字母一一进行组合，可以当成一个树形问题处理，拿 23 的组合来举例，图形如下：

    image.png

    问题就转化成了从根节点到空节点有多少条路径，也就是一个组合问题，选择回溯解决。

    回溯需要做的三件事：

    1. 确定回溯递归函数的参数
    2. 确定终止条件
    3. 确定函数内、遍历的通用逻辑

    递归函数参数

    第一个参数，为数字字符串；
    第二个参数，为下标，用来获取进行到的数字，会在递归调用时不断向后移；
    第三个参数，为已组合的字母字符串，在函数内遍历时使用，继续组合遍历到的字母。

    通用逻辑

    通过传入的数字，得到第一个数字对应的字母集合，遍历该集合，继续递归调用函数，得到第二个数字对应的字母集合，依次类推。

    每次递归都传入该次组合的字母字符串，以便继续递归可以叠加。待递归调用到条件结束，则回溯到上一层，继续下一个字母递归调用组合。

    终止条件

    结束条件为递归到最底层，也就是字母都取完为止，可通过移动的下标，判断和字符串的长度是否相同，来决定终止。

    代码：

    先定义一个哈希映射关系，存入每个数字对应的字母，跟上面的电话图一致，方便根据传入的数字找到对应的字母。

    1. let phone = {
    2.   "0":[],
    3.   "2" : ["a","b","c"],
    4.   "3" : ["d","e","f"],
    5.   "4" : ["g","h","i"],
    6.   "5" : ["j","k","l"],
    7.   "6" : ["m","n","o"],
    8.   "7" : ["p","q","r","s"],
    9.   "8" : ["t","u","v"],
    10.   "9" : ["w","x","y","z"]
    11. }
    12. var letterCombinations = function(digits) {
    13.   if(digits.length === 0) return []
    14.   const result = []
    16.   // digits 要查找的数字字符串；startIndex 进行到的数字下标；comString 已经组合的字符串
    17.   const loop = (digits, startIndex, comString) => {
    18.     if(startIndex === digits.length) {
    19.       result.push(comString)
    20.       return
    21.     }
    22.     const letter = digits[startIndex]  // 拿到对应的数字
    24.     if(letter === '0') return
    25.     // 字符不符合规定，抛错
    26.    if(!/[1-9]/.test(letter)){
    27.     throw new Error('不符合数字的规定')
    28.    }
    30.     const letterArr = phone[letter]  // 找到数字对应的字符集
    32.     // 循环数字对应的字符串集合
    33.     for(let i = 0; i< letterArr.length; i++){
    34.       // 继续递归，进行下一个数字
    35.       loop(digits, startIndex + 1, comString + letterArr[i])
    36.     }
    37.   }
    39.   loop(digits, 0, '')
    40.   return result
    41. };

    以上使用的是下标移动获取数字，也可以不断的截取字符串 digits.slice(1)，终止条件判断为字符串为空了。

    时间复杂度：暂无。

    思路二：广度优先
    **
    回溯方法是选择一条路径直到无法选取为止，然后再返回寻找下一个路径，直到底层，而广度优先是以层为维度，不断组合好每一层的字符串，然后继续向下一层组合，也就是一层一层的组合。

    画图示意：

    image.png

    该思路是维护一个数组队列，初始第一层是一个空的字符串；开始依次循环数字字符串，拿到数字对应的字母集合遍历，将上一层的字符串拼上该层的字母，新组合的字符入到队列，上一层的字符串出队。

    最后遍历完整个数字后，队列中字符串，就是遍历到底层的组合。

    代码：

    1. /**
    2.  * @param {string} digits
    3.  * @return {string[]}
    4.  */
    6. let phone = {
    7.   "0":[],
    8.   "2" : ["a","b","c"],
    9.   "3" : ["d","e","f"],
    10.   "4" : ["g","h","i"],
    11.   "5" : ["j","k","l"],
    12.   "6" : ["m","n","o"],
    13.   "7" : ["p","q","r","s"],
    14.   "8" : ["t","u","v"],
    15.   "9" : ["w","x","y","z"]
    16. }
    17. var letterCombinations = function(digits) {
    18.   if(digits.length === 0) return []
    19.   const result = []
    20.   result.push('') // 第一层
    21.   for(let i = 0; i < digits.length; i++){
    23.     let len = result.length;  // 层级节点数
    24.     let strArr = phone[digits[i]] // 数字对应的字母
    26.     for(let j = 0; j < len; j++){
    27.       let val = result.shift()  // 原来层级的节点出队
    28.       // 新的层级节点组合进入队列中
    29.       for(let k = 0; k < strArr.length; k++){
    30.         result.push(val + strArr[k])
    31.       }
    32.     }
    33.   }
    35.   return result
    36. };

    时间复杂度：暂无。

    总结：

    思路一是回溯法的应用，通过暴力的循环嵌套循环得到解，除此之外，类似这样的组合题，都基本使用这样的思路解决问题。