当前位置: 首页 > article >正文

leetcode17.电话号码的字母组合:字符串映射与回溯的巧妙联动

一、题目深度解析与字符映射逻辑

题目描述

给定一个仅包含数字 2-9 的字符串 digits,返回所有它能表示的字母组合。数字与字母的映射关系如下(与电话按键相同):

2: "abc", 3: "def", 4: "ghi", 5: "jkl", 
6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"

例如,输入 digits = "23",应返回 ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。题目要求:

  • 输出的字母组合需包含所有可能情况
  • 每个数字对应字母的不同组合都要考虑
  • 结果顺序不做要求

核心难点剖析

本题的关键在于如何根据数字字符串的每个字符,找到对应的字母集合,并通过回溯算法生成所有可能的组合。其中,数字与字母的映射关系需要通过数据结构记录,而回溯过程中的状态管理则是确保组合完整性的核心。

二、递归回溯解法的核心实现与逻辑框架

class Solution {// 数字到字母的映射数组,0和1无对应字母,用空字符串占位String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};List<String> res = new ArrayList<>();  // 存储所有结果组合StringBuilder sb = new StringBuilder();  // 记录当前组合public List<String> letterCombinations(String digits) {if (digits.length() == 0) {return res;  // 处理空字符串输入}backtracking(digits, 0);  // 从第一个数字开始回溯return res;  // 返回所有组合}public void backtracking(String digits, int num) {if (num == digits.length()) {res.add(sb.toString());  // 保存当前组合return;}// 获取当前数字对应的字母字符串String str = numString[digits.charAt(num) - '0'];for (int i = 0; i < str.length(); i++) {sb.append(str.charAt(i));  // 选择当前字母backtracking(digits, num + 1);  // 递归处理下一个数字sb.deleteCharAt(sb.length() - 1);  // 回溯:撤销当前选择}}
}

核心设计解析

  1. 字符映射数组
    • numString数组建立数字与字母的映射关系,通过numString[digits.charAt(num) - '0']可快速获取对应字母集合。其中,- '0'的操作将字符类型的数字转换为数组索引所需的整数类型。
  2. 结果与状态变量
    • res:使用ArrayList存储所有符合要求的字母组合。
    • sbStringBuilder用于高效构建当前组合,避免频繁字符串拼接带来的性能损耗。
  3. 递归终止条件
    • if (num == digits.length()):当处理完数字字符串的所有字符时,将当前sb记录的组合加入res,并结束当前递归分支。
  4. 回溯核心逻辑
    • 遍历当前数字对应的字母字符串,每次选择一个字母加入sb
    • 递归调用backtracking处理下一个数字。
    • 递归返回后,通过sb.deleteCharAt(sb.length() - 1)删除最后一个字母,回溯到上一状态,尝试其他可能的组合。

三、核心问题解析:字符串映射与回溯联动

1. 数字字符到字母集合的映射实现

numString数组是连接数字与字母的桥梁。以输入字符串"23"为例:

  • 处理第一个数字'2'时,numString[2 - '0']获取到"abc",即数字2对应的字母集合。
  • 处理第二个数字'3'时,numString[3 - '0']获取到"def"

这种映射方式通过数组下标直接定位,时间复杂度为O(1),相比使用Map等数据结构更加简洁高效。

2. 回溯算法的具体执行逻辑

backtracking方法中,回溯过程通过递归与状态回退实现:

  • 选择阶段
    sb.append(str.charAt(i));
    backtracking(digits, num + 1);
    
    每次从当前数字对应的字母集合中选择一个字母加入sb,并递归处理下一个数字,深入探索当前选择下的所有可能组合。
  • 回退阶段
    sb.deleteCharAt(sb.length() - 1);
    
    递归返回后,删除sb中最后一个字母,撤销当前选择,以便尝试该数字对应的其他字母,确保所有组合都能被枚举到。

3. 递归过程中的状态传递

在递归调用过程中,num参数记录当前处理的数字位置,sb则记录当前构建的组合状态。每一层递归都基于上一层的状态继续构建,确保组合的完整性和准确性。例如:

  • 当处理数字字符串"23"时,第一层递归处理数字2,第二层递归处理数字3。在第二层递归中,sb已包含第一层递归选择的字母(如'a'),在此基础上继续添加数字3对应的字母(如'd'),最终形成组合"ad"

四、递归流程深度模拟:以输入"23"为例

  1. 初始调用backtracking("23", 0)
    • num = 0,处理第一个数字'2'str = "abc"
  2. 选择字母'a'
    • sb.append('a'),此时sb = "a"
    • 递归调用backtracking("23", 1),处理第二个数字'3'str = "def"
    • 选择字母'd'sb.append('d'),此时sb = "ad",满足终止条件,将"ad"加入res
    • 回溯:sb.deleteCharAt(sb.length() - 1)sb变回"a",继续选择字母'e',形成"ae"并加入res,以此类推,完成数字3对应字母的所有组合。
  3. 回到数字2的处理
    • 撤销字母'a'的选择,sb.deleteCharAt(sb.length() - 1)sb清空。
    • 选择字母'b',重复上述递归过程,生成以'b'开头的所有组合(如"bd""be""bf")。
  4. 选择字母'c'
    • 同样进行递归与回溯,生成以'c'开头的所有组合(如"cd""ce""cf")。
  5. 最终结果
    res包含["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"],涵盖所有可能的字母组合。

五、算法复杂度分析

1. 时间复杂度

假设数字字符串digits的长度为n,每个数字平均对应m个字母(实际最多4个)。

  • 对于每个数字,都需要遍历其对应的字母集合,因此时间复杂度为 O ( m n ) O(m^n) O(mn) 。因为每个数字位置都有m种选择,总共n个位置,属于指数级复杂度。

2. 空间复杂度

  • 递归栈的深度最大为n,因此空间复杂度为 O ( n ) O(n) O(n)
  • res存储所有结果组合,最坏情况下,组合数量为 m n m^n mn,每个组合长度为n,因此res占用空间为 O ( n × m n ) O(n \times m^n) O(n×mn) 。整体空间复杂度主要由res决定,为 O ( n × m n ) O(n \times m^n) O(n×mn)

六、核心技术点总结:字母组合生成的关键要素

  1. 字符映射设计:通过数组建立数字与字母的高效映射,简化查找过程。
  2. 回溯状态管理:利用StringBuilder动态构建组合,并通过递归与回退操作确保枚举所有可能组合。
  3. 递归终止条件:根据数字字符串的处理进度判断是否完成一个组合的构建,及时保存结果。

七、常见误区与优化建议

1. 字符转换错误

  • 误区:遗漏- '0'操作,导致无法正确获取字母集合。
    String str = numString[digits.charAt(num)]; // 错误,未转换字符为数字
    
  • 正确做法:使用numString[digits.charAt(num) - '0']将字符类型数字转换为数组索引。

2. 回溯状态未完全回退

  • 误区:在递归返回后,未删除sb中的最后一个字母,导致后续组合错误。
    sb.append(str.charAt(i));
    backtracking(digits, num + 1);
    // 缺少 sb.deleteCharAt(sb.length() - 1);
    
  • 正确做法:确保在每次递归返回后,通过sb.deleteCharAt(sb.length() - 1)撤销当前选择。

3. 优化建议:迭代实现

若担心递归深度过深导致栈溢出,可以考虑使用迭代方式,借助队列或栈模拟递归过程。例如,使用队列存储中间状态,每次从队列中取出一个状态,扩展下一个数字对应的字母组合并重新入队,直至处理完所有数字。这种方式可以将空间复杂度优化为 O ( m n ) O(m^n) O(mn) ,避免递归栈的潜在风险。

通过对本题递归回溯解法的详细剖析,我们深入理解了如何利用字符串映射和回溯算法,高效生成电话号码对应的字母组合。这种解题思路在处理组合枚举类问题时具有广泛的应用价值,能够帮助我们解决更多类似的算法问题。

http://www.lryc.cn/news/2395010.html

相关文章:

  • Gartner《2025 年软件工程规划指南》报告学习心得
  • 数据库 | 使用timescaledb和大模型进行数据分析
  • 快速阅读源码
  • linux创建虚拟网卡和配置多ip
  • Java Class类文件结构
  • AI问答-Vue3+TS:reactive创建一个响应式数组,用一个新的数组对象来替换它,同时保持响应性
  • quasar electron mode如何打包无边框桌面应用程序
  • 【HW系列】—Windows日志与Linux日志分析
  • VIN码识别解析接口如何用C#进行调用?
  • 动态规划之网格图模型(一)
  • PCB设计实践(三十)地平面完整性
  • x86_64-apple-ios-simulator 错误
  • 使用ray扩展python应用之流式处理应用
  • IP证书的作用与申请全解析:从安全验证到部署实践
  • 第四十一天打卡
  • C++中指针常量和常量指针的区别
  • 深入解析向量数据库:基本原理与主流实现
  • VectorNet:自动驾驶中的向量魔法
  • PostgreSQL性能监控双雄:深入解析pg_stat_statements与pg_statsinfo
  • 【Linux系列】Linux/Unix 系统中的 CPU 使用率
  • C++语法系列之模板进阶
  • 基于图神经网络的自然语言处理:融合LangGraph与大型概念模型的情感分析实践
  • R 语言科研绘图 --- 热力图-汇总
  • 基于DFT码本的波束方向图生成MATLAB实现
  • vBulletin未认证API方法调用漏洞(CVE-2025-48827)
  • 解决访问网站提示“405 很抱歉,由于您访问的URL有可能对网站造成安全威胁,您的访问被阻断”问题
  • FeignClient发送https请求时的证书验证原理分析
  • UDP组播套接字与URI/URL/URN技术详解
  • 机器学习中的关键术语及其含义
  • 点云识别模型汇总整理