题目

题目来源：力扣（LeetCode）

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

image.png

示例 1：

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

示例 2：

输入：digits = “”
输出：[]
示例 3：

输入：digits = “2”
输出：[“a”,”b”,”c”]

广度优先搜索
维护一个队列。起初让空字符串入列，让当前层的字符串逐个出列，出列的字符串，会构建它下一层的新字母串，并入列。一层层地，考察到数字串的最末位，就到了最底一层，此时队列中存的是所有构建完毕的字母串，返回 queue 即可。

这里控制了层序遍历的深度，为 digits 的长度，而不是while(queue.length){…}那样让所有的节点入列出列，最后还会剩下最后一层节点，留在 queue 中返回。

  1. /**
  2.  * @param {string} digits
  3.  * @return {string[]}
  4.  */
  5. const letterCombinations = (digits) => {
  6.   if (digits.length == 0) return [];
  7.   const map = {
  8.     '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7':
  9.       'pqrs', '8': 'tuv', '9': 'wxyz'
  10.   };
  11.   const queue = [];
  12.   queue.push('');
  13.   for (let i = 0; i < digits.length; i++) { // bfs的层数，即digits的长度
  14.     const levelSize = queue.length; // 当前层的节点个数
  15.     for (let j = 0; j < levelSize; j++) { // 逐个让当前层的节点出列
  16.       const curStr = queue.shift(); // 出列
  17.       const letters = map[digits[i]];
  18.       for (const l of letters) {
  19.         queue.push(curStr + l); // 生成新的字母串入列
  20.       }
  21.     }
  22.   }
  23.   return queue; // 队列中全是最后一层生成的字母串
  24. };

深度优先搜索
其实就是将数字串“翻译”成字母串，找出所有的翻译可能。翻译第一个数字有 3 / 4 种选择，翻译第二个数字又有 3 / 4 种选择……
从首位翻译到末位，会展开成一棵递归树。指针 i 是当前考察的字符的索引。
当指针越界时，此时生成了一个解，加入解集，结束当前递归，去别的分支，找齐所有的解。

  1. const letterCombinations = (digits) => {
  2.   if (digits.length == 0) return [];
  3.   const res = [];
  4.   const map = {
  5.     '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7':
  6.       'pqrs', '8': 'tuv', '9': 'wxyz'
  7.   };
  8.   // dfs: 当前构建的字符串为curStr，现在“翻译”到第i个数字，基于此继续“翻译”
  9.   const dfs = (curStr, i) => { // curStr是当前字符串，i是扫描的指针
  10.     if (i > digits.length - 1) { // 指针越界，递归的出口
  11.       res.push(curStr); // 将解推入res
  12.       return; // 结束当前递归分支
  13.     }
  14.     const letters = map[digits[i]]; // 当前数字对应的字母
  16.     for (const letter of letters) { // 一个字母是一个选择，对应一个递归分支
  17.       dfs(curStr + letter, i + 1); // 选择翻译成letter，生成新字符串，i指针右移继续翻译（递归）
  18.     }
  19.   };
  20.   dfs('', 0); // 递归的入口，初始字符串为''，从下标0开始翻译
  21.   return res;
  22. };

原文题解：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/shou-hua-tu-jie-liang-chong-jie-fa-dfshui-su-bfsya/