17. 电话号码的字母组合 | LeetCode算法题解

题目描述

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

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

示例:

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

说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

来源：LeetCode

思路

递归。每个数字的对应字母，和剩余数字的组合，一一组合成新的组合即可。递归边界是空字符串""。注意空串的结果是[]。

解法

const alphaMap = {
  2: 'abc',
  3: 'def',
  4: 'ghi',
  5: 'jkl',
  6: 'mno',
  7: 'pqrs',
  8: 'tuv',
  9: 'wxyz'
}

/**
 * @param {string} digits
 * @return {string[]}
 */
const letterCombinations = digits => {
  if (digits.length === 0) return [];

  const result = [];
  const first = digits[0];
  const rest = digits.slice(1);

  for (let c of alphaMap[first]) {
    if (rest.length === 0) {
      result.push(c);
    } else {
      result.push(...letterCombinations(rest).map(i => `${c}${i}`))
    }
  }

  return result;
};