【回溯-1】17.电话号码的字母组合-北京尧图网络

题目描述给定一个仅包含数字2-9的字符串返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。示例 1输入digits 23输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2输入digits 2输出[a,b,c]解题思路方法一回溯DFS核心思路把问题看成树形结构每一层对应一个数字每个节点对应该数字的一个字母从根到叶子的路径就是一个组合具体过程示例digits 23 / | \ a b c ← 数字2的字母 /|\/|\/|\ d e f d e f d e f ← 数字3的字母所有路径: a→d, a→e, a→f b→d, b→e, b→f c→d, c→e, c→f回溯三步选择当前数字选一个字母递归处理下一个数字撤销回溯时删除当前字母代码实现class Solution { public: vectorstring letterCombinations(string digits) { if (digits.empty()) return {}; // 数字到字母的映射 vectorstring phone { , , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz }; vectorstring result; string path; backtrack(digits, 0, phone, path, result); return result; } private: void backtrack(string digits, int index, vectorstring phone, string path, vectorstring result) { // 终止条件处理完所有数字 if (index digits.size()) { result.push_back(path); return; } // 当前数字对应的字母 string letters phone[digits[index] - 0]; // 遍历每个字母 for (char c : letters) { path.push_back(c); // 选择 backtrack(digits, index 1, phone, path, result); // 递归 path.pop_back(); // 撤销 } } };复杂度分析设n是数字个数每个数字最多对应 4 个字母。维度复杂度说明时间复杂度O(4^n × n)最多 4^n 个组合每个组合长度 n空间复杂度O(n)递归栈深度 path 长度更精确时间复杂度 O(所有组合的总字符数) O(4^n × n)。关键细节1. 为什么用path而不是每次新建字符串用path作为全局路径通过push_back和pop_back实现选择与撤销避免频繁创建字符串。2. 为什么digits.empty()返回{}而不是{}题目要求空字符串返回空数组不是包含空字符串的数组。3. 回溯的模板void backtrack(参数) { if (终止条件) { 收集结果; return; } for (选择 : 当前可选项) { 做选择; backtrack(下一层); 撤销选择; } }方法二队列BFS迭代代码实现class Solution { public: vectorstring letterCombinations(string digits) { if (digits.empty()) return {}; vectorstring phone { , , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz }; vectorstring result {}; for (char d : digits) { vectorstring next; string letters phone[d - 0]; for (string s : result) { for (char c : letters) { next.push_back(s c); } } result move(next); } return result; } };复杂度时间 O(4^n × n)空间 O(4^n × n)缺点需要存储所有中间结果空间比回溯大。两种方法对比方法时间复杂度空间复杂度推荐度回溯DFSO(4^n × n)O(n)⭐⭐⭐⭐⭐队列BFSO(4^n × n)O(4^n × n)⭐⭐⭐总结要点说明核心思想回溯每个数字选一个字母递归下一层关键操作path.push_back(c)→ 递归 →path.pop_back()时间复杂度O(4^n × n)空间复杂度O(n)

【回溯-1】17.电话号码的字母组合

相关推荐

在现代 Web 自动化测试中，页面元素的加载往往具有异步性和不确定性

绿色矿山国标施行第2天：边缘AI矿山自查达标方案

上网第十四课：第二周复盘：宽带与组网 QA

更多资讯

MySQL IN查询大数据量优化：5种可落地方案与排障指南

MySQL日志体系与排障实战：从错误日志到binlog的深度解析

Docker 启动 MySQL 实战：从环境准备到备份恢复踩坑指南

Habitat-baselines v0.1.7 环境搭建与 PointNav 训练避坑指南

从零设计编程语言：词法分析、语法分析与解释器实现指南

基于Python的二维码识别系统源码数据库：从图像预处理到批量入库的完整实现

今日更新

45个经典Linux面试题：从命令到网络排障的完整考点解析

SAP生产预留实战指南：MB21/MB23/MB25协同与MRP集成

编译原理实验：递归下降分析器消除左递归与避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？