【LeetCode刷题日记】17.电话号码的字母组合

个人主页代码不加冰欢迎来访作者简介java后端学习者❄️个人专栏LeetCode刷题日记 苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰今天来到了我们每日的刷题环节昨天因为考试被耽误了一些也算是正式进入期末周了事情还是挺多的抽空发但还是会保持每日两更的时间就像海绵里的水挤挤总是有的这真是鲁迅说的哈哈。摘要本文介绍了LeetCode第17题电话号码的字母组合的解题思路。题目要求根据数字字符串返回所有可能的字母组合采用回溯算法解决多层循环问题。通过建立数字到字母的映射关系使用StringBuilder高效构建组合字符串并详细分析了回溯过程。代码实现了异常处理空输入和非法字符通过递归遍历所有可能的组合情况最终将结果存入列表返回。时间复杂度为O(3^N ×4^M)其中N和M分别对应3字母和4字母的数字个数。题目背景17.电话号码的字母组合给定一个仅包含数字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]的一个数字。题目解析从示例上来说输入23最直接的想法就是两层for循环遍历了吧正好把组合的情况都输出了。如果输入233呢那么就三层for循环如果2333呢就四层for循环.......大家应该感觉出和前面遇到的一样的问题就是这for循环的层数如何写出来此时又是回溯法登场的时候了。理解本题后要解决如下三个问题数字和字母如何映射两个字母就两个for循环三个字符我就三个for循环以此类推然后发现代码根本写不出来输入1 * #按键等等异常情况数字和字母如何映射可以使用map或者定义一个二维数组例如string letterMap[10]来做映射我这里定义一个二维数组回溯法来解决n个for循环的问题例如输入23抽象为树形结构如图所示图中可以看出遍历的深度就是输入23的长度而叶子节点就是我们要收集的结果输出[ad, ae, af, bd, be, bf, cd, ce, cf]。整体逻辑首先需要一个字符串s来收集叶子节点的结果然后用一个字符串数组result保存起来这两个变量我依然定义为全局。再来看参数参数指定是有题目中给的string digits然后还要有一个参数就是int型的index。注意这个index不是我们前面77.组合中的startIndex了。这个index是记录遍历第几个数字了就是用来遍历digits的题目中给出数字字符串同时index也表示树的深度。例如输入用例23两个数字那么根节点往下递归两层就可以了叶子节点就是要收集的结果集。那么终止条件就是如果index 等于 输入的数字个数digits.size了本来index就是用来遍历digits的。然后收集结果结束本层递归。首先要取index指向的数字并找到对应的字符集手机键盘的字符集。然后for循环来处理这个字符集以上就是这道题目的整体逻辑了看着还是很清晰的。然后就是具体的代码逻辑了跟我们上面的逻辑一一对应即可1.用数组存储private static final String[] PHONE_MAP { , // 0 , // 1 abc, // 2 def, // 3 ghi, // 4 jkl, // 5 mno, // 6 pqrs, // 7 tuv, // 8 wxyz // 9 };2.边界情况的处理if (digits null || digits.length() 0) { return result; }3.开始回溯// 开始回溯 backtrack(result, new StringBuilder(), digits, 0); return result;StringBuilder在这里的作用是动态构建字符串用来临时存储当前正在生成的字母组合。核心作用1. 高效拼接字符串回溯过程中需要频繁地添加和删除字符StringBuilder比普通字符串拼接效率高得多。java // 使用 StringBuilder高效 StringBuilder sb new StringBuilder(); sb.append(a); // 添加字符 sb.deleteCharAt(sb.length() - 1); // 删除最后一个字符 // 使用 String低效每次都会创建新对象 String str ; str a; // 创建新的 String 对象 str str.substring(0, str.length() - 1); // 又创建新对象2. 在回溯中保存临时路径看这个具体过程java // 初始状态 StringBuilder current new StringBuilder(); // current // 第1步选择 a current.append(a); // current a // 第2步选择 d current.append(d); // current ad // 到达底部将 ad 加入结果 result.add(current.toString()); // 转换为字符串 ad // 回溯删除 d current.deleteCharAt(current.length() - 1); // current a // 尝试下一个字母 e current.append(e); // current ae3.然后就是回溯代码的执行整体跟我们写的没什么区别注意一下代码细节digits.charAt(index) - 0将字符数字转换为整数java 2 - 0 2 // 字符相减得到整数 3 - 0 3 9 - 0 9 // 原理ASCII 码 // 0 的 ASCII 是 48 // 2 的 ASCII 是 50 // 50 - 48 2逐步执行的代码追踪java // 初始调用 letterCombinations(23) ├─ result [] ├─ digits 23, length2 └─ backtrack([], , 23, 0) // 第1次调用 backtrack (index0) ├─ index0, digits.length()2 → 继续 ├─ digit2, lettersabc ├─ 循环 i0: current.append(a) → currenta │ └─ 调用 backtrack([], a, 23, 1) │ ├─ index1 ! 2 → 继续 │ ├─ digit3, lettersdef │ ├─ 循环 i0: current.append(d) → currentad │ │ └─ 调用 backtrack([], ad, 23, 2) │ │ ├─ index2 digits.length() → result.add(ad) │ │ └─ 返回 │ ├─ current.deleteCharAt() → currenta │ ├─ 循环 i1: current.append(e) → currentae │ │ └─ 调用 backtrack([], ae, 23, 2) │ │ ├─ index2 digits.length() → result.add(ae) │ │ └─ 返回 │ ├─ current.deleteCharAt() → currenta │ ├─ 循环 i2: current.append(f) → currentaf │ │ └─ 调用 backtrack([], af, 23, 2) │ │ ├─ index2 digits.length() → result.add(af) │ │ └─ 返回 │ └─ current.deleteCharAt() → currenta │ ├─ 循环 i1: current.append(b) (类似过程) │ └─ 得到 bd, be, bf │ ├─ 循环 i2: current.append(c) (类似过程) │ └─ 得到 cd, ce, cf │ └─ 最终 result [ad,ae,af,bd,be,bf,cd,ce,cf]异常处理// 异常1: 输入为 null if (digits null) { return result; // 或抛出异常throw new IllegalArgumentException(Input cannot be null); } // 异常2: 空字符串 if (digits.length() 0) { return result; } // 异常3: 验证所有字符都是有效数字2-9 for (int i 0; i digits.length(); i) { char c digits.charAt(i); if (c 2 || c 9) { // 可以选择抛出异常或直接返回空结果 throw new IllegalArgumentException(Invalid digit: c . Only digits 2-9 are allowed.); // 或者: return result; // 静默返回空结果 } }题目答案class Solution { private static final String[] PHONE_MAP { , // 0 , // 1 abc, // 2 def, // 3 ghi, // 4 jkl, // 5 mno, // 6 pqrs, // 7 tuv, // 8 wxyz // 9 }; public ListString letterCombinations(String digits) { ListString result new ArrayList(); if (digits null || digits.length() 0) { return result; } backtrack(result, new StringBuilder(), digits, 0); return result; } private void backtrack(ListString result, StringBuilder current, String digits, int index) { if (index digits.length()) { result.add(current.toString()); return; } // 获取当前数字对应的字母字符串 String letters PHONE_MAP[digits.charAt(index) - 0]; for (int i 0; i letters.length(); i) { current.append(letters.charAt(i)); backtrack(result, current, digits, index 1); current.deleteCharAt(current.length() - 1); } } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励