【回溯-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)