题目概览

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= digits.length <= 4
• digits[i]是范围['2', '9']的一个数字。

来源：17. 电话号码的字母组合 - 力扣（LeetCode）

解题分析

方法：回溯

先用一个哈希表存储数字和字符串的映射。
令当前数字的索引为 i，用集合存储之前拼过的字符前缀 prefix，每次递归我们遍历 i 位置的数字对应的字符串，将当前字符存入 prefix 中，然后继续递归遍历 i + 1 的数字直到 i == n - 1，这样得的 prefix 就是结果之一，递归完成后回溯到上一层，将当前字符移除，继续遍历下一个字符，重复操作，直到遍历完成。

时间复杂度：O(4^m * 3^n) ( m 为字符串长度为 4 的数字个数，n为字符串长度为 3 的数字个数）
空间复杂度：O(m+n)

class Solution { public static Map<Character, String> mapping = new HashMap<>(); static { mapping.put('2', "abc"); mapping.put('3', "def"); mapping.put('4', "ghi"); mapping.put('5', "jkl"); mapping.put('6', "mno"); mapping.put('7', "pqrs"); mapping.put('8', "tuv"); mapping.put('9', "wxyz"); } public List<String> letterCombinations(String digits) { List<String> result = new ArrayList<>(); backTracking(digits, result, 0, digits.length(), new StringBuffer()); return result; } public void backTracking(String digits, List<String> result, int index, int n, StringBuffer prefix) { if (index == n) { result.add(prefix.toString()); return; } String letters = mapping.get(digits.charAt(index)); for (int i = 0; i < letters.length(); ++i) { prefix.append(letters.charAt(i)); backTracking(digits, result, index + 1, n, prefix); prefix.deleteCharAt(index); } } }