电话号码的字母组合
力扣原题链接
问题描述
给定一个仅包含数字 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);}}
}
通过回溯算法，我们可以找出给定数字字符串能表示的所有字母组合。
