[LeetCode：Letter Combinations of a Phone Number] | 刷题打卡

真心求大家关注和点赞，原创不易，你们的支持是我写作的最大动力！

题目描述

给你一个只包括 2-9 数字的字符串，返回这些数字能表示的所有字母的组合，返回结果可以任意顺序，数字和字母的映射关系如下如：（老式手机按键）

例一：

输入: digits = "23"
输出: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

例二：

输入: digits = ""
输出: []

例三：

输入: digits = "2"
输出: ["a","b","c"]

思路分析

我觉得这道题可以改一改：你是一位有志之士，组织派你破解敌方的信号，你在他们手机上安装了一个能窃听哪个键被按下的装置，你需要通过被按下的按键来确定敌方所有可能输入的信息，最后将敌方一举拿下。算了，不扯了...

这是一道回溯题，考察大家对递归的运用

首先需要考虑的是整理出来数字和字母的映射关系，我已经帮你们做好了：

const mapping = {
  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"],
};

然后就是开始写回溯算法，我自己写回溯算法的心得如下：

var xxx = function () {
  const result = [];
  const backtrace = (arr,cur) => {
    // 递归出口，需要往 result 里面 push 结果了
   // 如何进行回溯和递归
  };
  backtrace(arr,cur);
  return result;
};

1. 首先得有个 result 数组保存最终结果
2. 然后是需要进行递归的函数，也就是回溯算法的主体
3. 调用函数，传入一个初始值
4. 将 result 结果返回

重点来说下步骤二和步骤三：

• 步骤二的函数入参一般有两个，一个是待选数据集合 arr，另一个是当前已经选的值 cur，函数主体一般会先写递归出口，这时需要把生成的中间结果 push 到 result 数组中，然后遍历待选数据集合，把上一次的值和当前值拼接起来，传入下一次的递归
• 步骤三一般需要传入一个初始状态

就拿这道题来说：

• 待选数据集合是用户按的 2-9 的数字，因为题目传入的是字符串，所以需要我们来处理成数组形式，初始的时候就是：digits.split("")
• 已经选择的结果是个字符串，例如上例一中的 "ad"，初始的时候是个空字符串

在递归主体，我们需要遍历传入的 arr，拿到所有的数，然后通过定义的 mapping 表映射出和这个数字对应的所有的字母，遍历这个字母列表，把上次的结果和当前的字符拼接在一起作为已选的值，传入下一次递归过程，同时待选数据集合则要删掉一个

递归出口也容易看出，当 cur 的长度和 digits 的长度相同时表示递归结束，此时需要将一次结果 push 到结果数组中，最终代码如下：

AC 代码

var letterCombinations = function (digits) {
  const result = [];
  const backtrace = (arr, current) => {
    if (current.length === digits.length && current !== "") {
      result.push(current);
      return;
    }
    for (let i = 0; i < arr.length; i++) {
      for (let j = 0; j < mapping[arr[i]].length; j++) {
        backtrace(arr.slice(i + 1), current + mapping[arr[i]][j]);
      }
    }
  };
  backtrace(digits.split(""), "");
  return result;
};

总结

回溯算法主要操作两个变量：一是待选数组，二是当前已选择的内容，每次递归时遍历所有可能的值，把上一次选择的值和这次的值拼在一起作为新的值进行下一次递归，在递归结束时把当前值 push 到结果数组中。

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情