17. 电话号码的字母组合

---

题目

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

示例： 示例 1:

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

示例 2:

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

示例 3:

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

---

解题思路

核心方法

回溯法：

1. 数字字母映射：使用数组存储每个数字对应的字母，例如 map[2] = "abc"。
2. 路径选择：维护一个 StringBuilder 存储当前已选择的字母组合。
3. 递归终止条件：当当前深度等于输入数字字符串的长度时，将当前字母组合加入结果列表。
4. 回溯过程：遍历当前数字对应的所有字母，将其加入 StringBuilder，递归进入下一层（深度+1）；递归返回后，删除该字母，继续尝试其他字母。

---

代码实现

回溯法（Java）

import java.util.*;

class Solution {
    List<String> ans = new ArrayList<>();
    StringBuilder temp = new StringBuilder();
    String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) return ans;
        dfs(digits, 0);
        return ans;
    }
    
    public void dfs(String digits, int depth) {
        if (digits.length() == depth) {
            ans.add(temp.toString());
            return;
        }
        String curr = map[digits.charAt(depth) - '0'];
        for (int i = 0; i < curr.length(); i++) {
            temp.append(curr.charAt(i));
            dfs(digits, depth + 1);
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}

---

复杂度分析

• 时间复杂度：O(3^m * 4^n)，其中 m 是对应 3 个字母的数字（2、3、4、5、6、8）的数量，n 是对应 4 个字母的数字（7、9）的数量。每个数字的字母选择相互独立，总组合数为各数字字母数的乘积。
• 空间复杂度：O(m + n)，递归栈的深度为输入数字的长度，StringBuilder 的空间也为输入数字的长度。

---

总结

1. 回溯法是解决这类组合生成问题的经典方法，通过递归和状态回溯，能够高效生成所有可能的字母组合。
2. 数字字母映射数组的设计简化了字母的查找过程，提高了代码的可读性。
3. 该方法适用于输入长度较短的场景（题目限制 1 <= digits.length <= 4），性能表现良好。

---