[Java·算法·中等]LeetCode17. 电话号码的字母组合

题目

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

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

示例

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

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

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

分析思路1

可以使用递归的方式来实现。
使用了一个数组来保存数字与字母的对应关系。在递归过程中，我们不断地向已有的组合中添加新的字母，直到所有数字都被处理完毕。

题解1

class Solution {// 定义数组存储每个数字对应的字母,下标0和1均为空private final String []  arr = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};public List<String> letterCombinations(String digits) {List<String> res = new ArrayList<>();if(digits == null || digits.length() == 0){return res;}backtrack(digits, 0, "", res);return res;}private void backtrack(String digits, int index, String combination, List<String> res){if(index == digits.length()){res.add(combination);return;}// 利用char变量使用 ASCII进行算术运算这一特征，可以得到一种间接计算获取数值的方法// '0'-'9'  ASCII 为 48-57，且顺序一致，因而char数字之间的差值等于数字之间的差值String letters = arr[digits.charAt(index) - '0'];for(int i = 0; i < letters.length(); i++){backtrack(digits, index + 1, combination + letters.charAt(i), res);}}
}

执行结果

分析思路2

使用回溯算法进行求解。
首先，定义一个哈希表，将每个数字对应的字母存入其中，以便后续查找。
然后，定义一个结果列表 res，用于存储所有的字母组合。
接着，调用回溯函数 backtrack，该函数的参数为当前要处理的电话号码字符串 digits、当前要处理的字符索引 index、当前已经组合好的字母字符串 combination 和结果列表 res。
在回溯函数中，首先判断当前要处理的字符索引是否等于电话号码字符串的长度，如果是，说明已经处理完了所有的字符，此时将当前已经组合好的字母字符串 combination 添加到结果列表 res 中，并返回。
如果当前要处理的字符索引小于电话号码字符串的长度，说明还有字符需要处理。首先从哈希表中获取当前数字对应的字母列表 letters，然后依次枚举其中的每个字母，并将其添加到当前已经组合好的字母字符串 combination 的末尾，然后递归调用回溯函数 backtrack，处理下一个字符。
在递归返回后，需要将当前已经组合好的字母字符串 combination 的末尾字符删除，以便后续枚举其他字母。

题解2

class Solution {private Map<Character, String> phone = new HashMap<Character, String>() {{put('2', "abc");put('3', "def");put('4', "ghi");put('5', "jkl");put('6', "mno");put('7', "pqrs");put('8', "tuv");put('9', "wxyz");}};public List<String> letterCombinations(String digits) {List<String> res = new ArrayList<String>();if (digits.length() == 0) {return res;}backtrack(digits, 0, new StringBuilder(), res);return res;}private void backtrack(String digits, int index, StringBuilder combination, List<String> res) {if (index == digits.length()) {res.add(combination.toString());return;}char digit = digits.charAt(index);String letters = phone.get(digit);for (int i = 0; i < letters.length(); i++) {combination.append(letters.charAt(i));backtrack(digits, index + 1, combination, res);combination.deleteCharAt(index);}}
}

执行结果