LeetCode 17电话号码的字母组合：回溯算法（DFS）详解-云帆数科

一、题目来源与描述题目来源LeetCode 第 17 题 - 电话号码的字母组合 (Medium)题目描述给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下与电话按键相同。注意1不对应任何字母。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]二、核心算法回溯法Backtracking / DFS1. 思路解析这道题本质上是一道排列组合问题。每一个数字对应多个字母我们需要从每个数字对应的字母集合中挑选一个字母拼接成一个完整的字符串。由于字符串的长度不定最多为 4且需要枚举所有可能的组合暴力循环嵌套 for 循环无法动态适应长度。因此我们需要使用回溯算法深度优先搜索 DFS。回溯法的核心思想将问题抽象为一棵决策树N 叉树。树的深度由输入字符串digits的长度决定。节点的分支由当前数字对应的字母数量决定3 或 4 个分支。我们通过递归沿着树的深度遍历当到达叶子节点即处理完所有数字时记录当前路径然后“回溯”到上一层尝试其他分支。2. 回溯三步曲确定递归函数的参数与返回值参数需要包含给定的数字字符串digits以及一个索引index用来标记当前遍历到了哪一个数字。返回值不需要返回值结果直接存入全局变量或类成员变量中。确定终止条件当index digits.size()时说明已经处理完了所有的数字此时将当前拼接好的字符串加入结果集并结束本层递归。确定单层遍历逻辑获取当前index指向的数字对应的字母集letters。使用for循环遍历letters将当前字母加入当前路径path。递归调用下一层index 1。回溯操作将当前字母从path中移除以便尝试下一个字母。三、代码实现 (C)class Solution { public: // 1. 建立数字到字母的映射表 (使用数组下标直接映射效率极高) const string phone_map[10] { , // 0 , // 1 abc, // 2 def, // 3 ghi, // 4 jkl, // 5 mno, // 6 pqrs, // 7 tuv, // 8 wxyz // 9 }; // 存放最终结果和当前路径的成员变量 vectorstring result; string current_path; // 2. 回溯函数 void backtracking(const string digits, int index) { // 终止条件index 走到头了说明生成了一个完整组合 if (index digits.size()) { result.push_back(current_path); return; } // 获取当前数字对应的字符集 int digit digits[index] - 0; // 字符转整数 string letters phone_map[digit]; // 遍历当前数字对应的所有字母 for (int i 0; i letters.size(); i) { current_path.push_back(letters[i]); // 处理节点加入 backtracking(digits, index 1); // 递归进入下一层 current_path.pop_back(); // 回溯撤销处理 } } // 3. 主函数 vectorstring letterCombinations(string digits) { // 每次调用前清空全局状态 result.clear(); current_path.clear(); // 特殊情况如果输入为空直接返回空数组 if (digits.empty()) { return result; } backtracking(digits, 0); return result; } };四、复杂度分析时间复杂度O(3M×4N)其中M是输入中对应 3 个字母的数字个数例如 2, 3, 4, 5, 6, 8N是输入中对应 4 个字母的数字个数例如 7, 9MN 是输入数字的总个数。一共有 3M×4N种组合每种组合需要 O(1)的时间拼接字符串在 C 中push_back和pop_back均摊为 O(1)。空间复杂度O(MN)主要取决于递归调用栈的深度最大深度为输入字符串的长度即 MN。此外结果集result的空间不计入算法的辅助空间复杂度。五、递归与回溯模板总结本题是标准的回溯模板void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择本层集合中元素树中节点孩子的数量就是集合的大小) { 处理节点; backtracking(路径选择列表); // 递归回溯撤销处理结果; } }

企业数字化 ERP 产品动态

相关推荐

vscode 插件 CMake Tools 配置工具链：用 TaoToken 统一 Key 打通 settings.json 骨架

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 1:26:02

I3C协议原理与RK3576硬件实战：从10倍提速到DAA/IBI落地

1. 为什么说 I3C 比 I2C 快 10 倍？这不是营销话术，而是协议层重构带来的真实吞吐跃迁最近在 RK3576 平台做传感器子系统集成时，反复被客户问到一个问题：“你们说 I3C 比 I2C 快 10 倍，是实测数据还是理论值&#xff1f… · 2026/9/26 1:26:02

破解120分钟限制的VideoDownloadHelper插件

简介：VideoDownloadHelper是一款允许无限制下载时长视频内容的浏览器插件 ，适用于Firefox、Chrome等浏览器。它能自动检测网页中的视频和音频资源，并提供下载。插件支持多种格式，如MP4、FLV、WebM、MP3等，并具备智能分… · 2026/9/26 1:26:02

采购部绩效考核关键指标与优化路径

采购部的绩效考核是企业运营管理中的重要环节，通过对采购效率、成本控制、商品质量和库存管理等方面的严格评估，能够全面了解采购部门的工作表现和对公司业务的支持程度。为了确保考核的科学性和有效性，不同考核周期下的指标定义和计算方法各有特色，既能反映采购工作的实际… · 2026/9/26 2:13:31

Awvs 压缩包安装部署全流程：从解压到首次扫描的避坑指南

鸿蒙PC版系统镜像安装全攻略：从镜像校验到BIOS设置避坑指南

Claudeception：让Claude Code持续学习技能，沉淀可复用工作流

Claudeception这个词我第一次看到的时候，第一反应是“套娃”——把Claude Code扔给Claude Code去优化，听起来确实像盗梦空间里的梦中梦。但这个概念真落到项目里，解决的是一个特别朴素的问题：Claude Code每次对话结束之后&#xf… · 2026/9/26 2:13:25

TIA Portal WinCC画面下载与启动全流程详解：从HMI到PC站

做自动化项目调试，被新同事问得最多的问题之一，就是 TIA Portal 里面 WinCC 画面组态好了，怎么下载到设备，下载完又怎么启动。这个问题看着基础，里面藏着不少坑：有人下载时老是找不到设备，有人下… · 2026/9/26 2:13:19

接待部经理绩效考核指标量表与综合评估

接待部门作为企业中至关重要的职能部门，其工作直接影响着客户的满意度和企业的整体形象。接待部经理不仅需要有效安排和执行工作计划，还要在费用控制、服务质量提升等方面展现出卓越的管理能力。因此，如何通过科学的绩效考核体系全面评估接待部经理的工作表现，成为管理层关… · 2026/9/26 2:13:19

数据库课后习题答案别硬背：当测试用例集刷，效率翻倍

简介：万常选版《数据库原理与设计》课后习题答案资源，覆盖第2至6章及第9章，适合正在学习关系模型、数据库建模、关系数据理论与模式求精的本科生、自学者作为复习与自测材料。压缩包共7个文件，含3个doc参考答案、2个sql示例脚本、… · 2026/9/26 0:00:21

OpenClaw 替代品？Hermes Agent 踩坑实录：macOS 飞书接入 TaoToken 配置

向下兼容与向上兼容：接口设计中的兼容性策略与工程实践

一次版本升级事故，是很多团队绕不过去的坎。线上环境里，服务端明明已经上线了新版接口，老的移动端还在照着旧文档传参数。请求一到网关，校验直接拒绝，用户操作失败，客服群炸了锅，开发群里开始互… · 2026/9/26 0:00:46

LeetCode 17电话号码的字母组合：回溯算法（DFS）详解

相关推荐

了解更多？预约专属演示