17.电话号码的字母组合

题目:17.电话号码的字母组合

给定一个仅包含数字 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'] 的一个数字。

思路

这个问题可以使用回溯算法来解决。由于每个数字都映射到多个字母，需要找到所有可能的组合情况。可以通过回溯算法递归地构建这些组合。

步骤

1. 构建数字与字母的映射关系：将每个数字对应的字母存储在字典中。
2. 使用回溯法生成所有可能的字母组合：从第一个数字开始，依次选择该数字对应的字母，递归地处理剩下的数字。
3. 终止条件：当处理完所有的数字时，得到一个完整的组合，将其加入结果列表。

• 时间复杂度:O(n)
• 空间复杂度:O(n)

代码

public List<String> letterCombinations(String digits) {
    List<String> result = new LinkedList<>();
    // 如果输入为空，返回空列表
    if (digits == null || digits.isEmpty()) {
        return result;
    }
    // 建立数字到字母的映射
    Map<Character, String> phoneNumber = new HashMap<>();
    phoneNumber.put('2', "abc");
    phoneNumber.put('3', "def");
    phoneNumber.put('4', "ghi");
    phoneNumber.put('5', "jkl");
    phoneNumber.put('6', "mno");
    phoneNumber.put('7', "pqrs");
    phoneNumber.put('8', "tuv");
    phoneNumber.put('9', "wxyz");
    // 开始回溯搜索
    dfs(0, phoneNumber, result, digits, new StringBuilder());
    return result;
}

// 回溯函数
private void dfs(int index, Map<Character, String> phoneNumber, List<String> result, String digits, StringBuilder current) {
    // 当已经处理到数字末尾时，收集当前组合
    if (index == digits.length()) {
        result.add(current.toString());
        return;
    }
    char digit = digits.charAt(index);

    String letters = phoneNumber.get(digit);
    // 遍历该数字对应的每个字母
    for (int i = 0; i < letters.length(); i++) {
        // 将该字母添加到当前组合
        current.append(letters.charAt(i));
        // 递归处理下一个数字
        dfs(index + 1, phoneNumber, result, digits, current);
        // 回溯，撤销上一步的选择
        current.deleteCharAt(current.length() - 1);
    }
}