Letter Combinations of a Phone Number（电话号码的字母组合）

题目 / Problem

中文： 给定一个只包含数字 2-9 的字符串 digits，返回这些数字在电话键盘上能够表示的所有字母组合。答案可以按任意顺序返回。

数字 1 不对应任何字母。

English: Given a string containing digits from 2 to 9, return all possible letter combinations that the number could represent. The answer may be returned in any order.

Digit 1 does not map to any letters.

数字与字母映射 / Digit-to-Letter Mapping

示例 / Examples

Example 1

Input:  digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

数字 2 对应 abc，数字 3 对应 def。从两组字母中各选择一个，得到 3 × 3 = 9 种组合。
Digit 2 maps to abc, and digit 3 maps to def. Choosing one letter from each group produces 3 × 3 = 9 combinations.

Example 2

Input:  digits = "2"
Output: ["a","b","c"]

约束 / Constraints

• 1 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 中的数字。
  Each digits[i] is a digit in the range ['2', '9'].

解题思路：回溯 / Approach: Backtracking

每个输入数字都对应一组可选字母。需要从每组中选择一个字母，并把选择结果拼接成完整字符串。
Each input digit corresponds to a group of possible letters. Choose one letter from every group and concatenate the choices into a complete string.

使用 index 表示当前正在处理 digits 中的哪个数字，使用 path 保存已经选择的字母：
Use index for the digit currently being processed and path for the letters selected so far:

1. 读取 digits[index] 对应的所有字母。
   Read all letters mapped from digits[index].
2. 依次选择其中一个字母并加入 path。
   Choose each letter in turn and append it to path.
3. 递归处理下一个数字。
   Recursively process the next digit.
4. 递归返回后撤销当前选择。
   Undo the current choice after recursion returns.
5. 当 index === digits.length 时，得到一个完整组合。
   When index === digits.length, one complete combination has been formed.

回溯搜索树 / Backtracking Search Tree

对于 digits = "23"：
For digits = "23":

""
├── "a"
│   ├── "ad"
│   ├── "ae"
│   └── "af"
├── "b"
│   ├── "bd"
│   ├── "be"
│   └── "bf"
└── "c"
    ├── "cd"
    ├── "ce"
    └── "cf"

树的深度等于数字字符串长度，每个叶子节点都是一个答案。
The tree depth equals the number of input digits, and every leaf is one answer.

JavaScript 实现 / JavaScript Implementation

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

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

  const result = [];
  const path = [];

  function backtrack(index) {
    if (index === digits.length) {
      result.push(path.join(""));
      return;
    }

    const letters = lettersByDigit[digits[index]];

    for (const letter of letters) {
      // 做出选择 / Make a choice
      path.push(letter);

      // 处理下一个数字 / Process the next digit
      backtrack(index + 1);

      // 撤销选择 / Undo the choice
      path.pop();
    }
  }

  backtrack(0);
  return result;
}

虽然当前题目约束保证 digits 非空，代码仍处理了空字符串，使函数在更通用的输入下返回 []。
Although the current constraints guarantee a non-empty input, the implementation still handles an empty string and returns [] for robustness.

执行过程 / Walkthrough

以 digits = "23" 为例：
For digits = "23":

每次保存完整组合后，通过 path.pop() 返回上一层并尝试下一个字母。
After storing a complete combination, path.pop() returns to the previous level so the next letter can be tried.

为什么不需要去重？ / Why Is Deduplication Unnecessary?

每一层只负责一个固定位置，每条搜索路径对应一组唯一的位置选择。由于每个数字映射中的字母互不相同，不同路径不会产生相同字符串。
Each level controls one fixed position, and every search path represents a unique sequence of positional choices. Since letters within each digit mapping are distinct, separate paths cannot produce the same string.

因此不需要使用 Set 对结果去重。
Therefore, no Set is needed to deduplicate the result.

复杂度 / Complexity

设 n = digits.length。数字 7 和 9 各映射到四个字母，其他数字映射到三个字母，因此组合数量最多为 4^n。
Let n = digits.length. Digits 7 and 9 map to four letters, while the others map to three, so there are at most 4^n combinations.

每个结果字符串的长度为 n：
Each result string has length n:

• 时间复杂度 / Time: O(n × 4^n)，包括构造所有输出字符串。
  O(n × 4^n), including construction of all output strings.
• 辅助空间 / Auxiliary space: O(n)，用于递归栈和当前路径，不包括返回结果。
  O(n) for the recursion stack and current path, excluding output.
• 结果空间 / Output space: O(n × 4^n)

易错点 / Common Pitfalls

• 数字 7 对应 pqrs，数字 9 对应 wxyz，它们各有四个字母。
  Digits 7 and 9 map to four letters: pqrs and wxyz.
• 每个组合必须为每个输入数字选择恰好一个字母。
  Every combination must choose exactly one letter for every input digit.
• 递归结束条件是 index === digits.length。
  The recursion ends when index === digits.length.
• 递归返回后必须执行 path.pop() 撤销选择。
  Call path.pop() after recursion to undo the choice.
• 空输入应返回 []，而不是包含空字符串的 [""]。
  For an empty input, return [], not [""].
• 题目只包含数字 2-9，不需要为 0 和 1 建立字母映射。
  Inputs contain only digits 2-9, so no letter mappings are needed for 0 or 1.