电话号码字母组合 - wangshengliang

题目#

给定一个仅包含数字 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 <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

解题思路#

其实这道题和前面的组合那道题基本上是一致的，只不过序列和组合个数没有明确给出。

🤔 思考：序列是什么？

这里的序列其实就是数字映射的字母序列。2 映射的字母是 ‘abc’，3 映射的字母是 ‘def’，因此整个 ‘23’ 字符串所映射的字母序列就是 ‘abcdef’

回溯整体框架

function backtrack(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtrack(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

🤔思考：是否需要剪枝？

剪枝主要是用于排除“无解”或者“没有更优解”的分支，从而减少搜索的空间。在这道题中，所有的分支都是一个有效的、合法的字母组合，所以不需要剪枝。

代码实现

/**
 * digits - 是一个字符串，该字符串包含数字 2-9
 * returns - 所有字母的组合
 */
function letterCombinations(digits) {
  const result = [] // 存储最终结果的数组

  if (!digits || digits.length === 0) return result

  // 数组下标和字母的对应关系
  const numMap = [
    '', // 0 - 不使用
    '', // 1 - 不使用
    'abc', // 2
    'def', // 3
    'ghi', // '4'
    'jkl', // '5'
    'mno', // '6'
    'pqrs', // '7'
    'tuv', // '8'
    'wxyz', // '9'
  ]

  /**
   * index - 当前处理到了第几位 "23" 需要先处理第 0 位 2，然后处理第 1 位就是 3
   * path - 已经组合好的字母序列
   */
  function backtrack(index, path) {
    if (index === digits.length) {
      // 进入此分支，说明所有数字都已经处理完了
      result.push(path.join('')) // 将 path 数组拼成字符串，推入到结果数组里面
      return
    }

    const digit = digits[index] // 2
    const letters = numMap[parseInt(digit)] // 获取当前数字所对应的字母序列

    // 遍历字母序列
    for (let i = 0; i < letters.length; i++) {
      path.push(letters[i]) // 将一个字母推入到path中
      // 递归下一位数字
      backtrack(index + 1, path)
      path.pop() // 移除最后一个字母
    }
  }
  backtrack(0, [])

  return result
}

-EOF-