JAVA练习330- 电话号码的字母组合

题目概览给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。示例 1输入digits 23输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2输入digits 2输出[a,b,c]提示1 digits.length 4digits[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(mn)class Solution { public static MapCharacter, 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 ListString letterCombinations(String digits) { ListString result new ArrayList(); backTracking(digits, result, 0, digits.length(), new StringBuffer()); return result; } public void backTracking(String digits, ListString 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); } } }