java电话号码的字母组合（力扣Leetcode17）

电话号码的字母组合

力扣原题链接

问题描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

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

示例

示例 1：

输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2：

输入：digits = “”
输出：[]

示例 3：

输入：digits = “2”
输出：[“a”,“b”,“c”]

解题思路

这是一个典型的回溯算法问题。我们需要根据数字到字母的映射，将给定的数字字符串转换为所有可能的字母组合。

代码思路

构建数字到字母的映射表： 首先构建一个数组 LETTERS，用于存储数字到字母的映射，数组下标代表数字，数组元素代表对应的字母字符串。
初始化结果列表： 创建一个空的列表 combinations，用于存储最终的字母组合结果。
回溯搜索： 定义一个回溯函数 backtrack，其参数包括当前数字字符串 digits、当前处理的索引 index、当前的字母组合路径 path。
结束条件： 如果当前路径长度等于数字字符串的长度，则将当前路径加入结果列表，并返回。
选择列表： 获取当前数字对应的字母集合。
遍历选择： 遍历当前数字对应的字母集合，对每个字母进行递归搜索。
做出选择： 将当前字母加入路径。
递归进入下一层： 递归调用回溯函数，传入新的索引 index+1，继续搜索下一个数字对应的字母。
撤销选择： 回溯到上一层时，将当前选择的字母从路径中删除，继续遍历下一个字母。

请添加图片描述

Java解题

垃圾版

class Solution {
    Map<Integer, String> en = new HashMap<>(); 
    List<String> res = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits.equals("")|| digits == null) return res;
        en.put(0,"");
        en.put(1,"");
        en.put(2,"abc");
        en.put(3,"def");
        en.put(4,"ghi");
        en.put(5,"jkl");
        en.put(6,"mno");
        en.put(7,"pqrs");
        en.put(8,"tuv");
        en.put(9,"wxyz");
        String s = new String();
        backtract(digits,0,s);
        return res;
    }
    public void backtract(String digits,int index,String s){
        if(index == digits.length()){
            res.add(s);
            return;
        }
        String arr = en.get(Integer.parseInt(String.valueOf(digits.charAt(index))));
        for(int i =0 ;i<arr.length();i++){
            s += arr.charAt(i);
            backtract(digits,index+1,s);
            s = s.substring(0,s.length()-1);
        }
    }
}

优化版

直接使用String 数组就行，数组下标和元素就是一个二维映射，不用使用hash表的计算查询。
收集结果使用StringBuilder，避免String进行拼接，裁剪时的新建。

import java.util.*;

class Solution {
    // 存储数字到字母的映射关系
    private static final String[] LETTERS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    // 存储最终结果的列表
    private List<String> combinations = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return combinations;
        }
        backtrack(digits, 0, new StringBuilder());
        return combinations;
    }

    // 回溯函数
    private void backtrack(String digits, int index, StringBuilder path) {
        // 如果路径长度等于数字字符串的长度，将路径加入结果列表
        if (index == digits.length()) {
            combinations.add(path.toString());
            return;
        }
        // 获取当前数字对应的字母集合
        String letters = LETTERS[digits.charAt(index) - '0'];
        // 遍历当前数字对应的字母集合
        for (char letter : letters.toCharArray()) {
            // 做出选择
            path.append(letter);
            // 递归进入下一层决策树
            backtrack(digits, index + 1, path);
            // 撤销选择
            path.deleteCharAt(path.length() - 1);
        }
    }
}