【Hot 100 刷题计划】 LeetCode 17. 电话号码的字母组合 | C++ 回溯算法经典模板
LeetCode 17. 电话号码的字母组合
📌 题目描述
题目级别：中等
给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1:
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]示例 2:
输入：digits = ""
输出：[]
💡 破题思路：DFS 深度优先搜索
这道题是经典的组合排列问题。核心思想是将按键数字映射到对应的字母表，然后通过深度优先搜索 (DFS)逐层展开。
本套解法亮点（极简传值法）：
- 精准映射：在全局定义一个
let数组，前两个元素设为空字符串""。这样可以直接通过digs[u] - '0'获取数字，完美对应数组下标，省去了复杂的偏移量计算。 - 传值拼接：在递归函数的参数中直接传递拼接好的字符串
strr + let[num][i]。这种写法极其直观，代码量极少，非常符合人类顺着树形结构往下探索的直觉逻辑。 - 边界拦截：针对 LeetCode 的特殊空串测试用例
""，在主函数入口处进行if (digits.empty())特判拦截，防止误生成包含空字符串的数组。
💻 C++ 代码实现 (保留原汁原味)
classSolution{public:intn;vector<string>res;// 巧妙设计：下标直接对应数字，0和1为空vector<string>let={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};vector<string>letterCombinations(string digits){n=digits.size();// 唯一需要注意的致命陷阱：特判空字符串if(n==0)returnres;string str="";dfs(digits,str,0);returnres;}voiddfs(string digs,string strr,intu){// 递归终止条件：当前组合的长度等于输入的数字长度if(strr.size()==digs.size()){res.push_back(strr);return;}// 利用直接映射获取当前数字intnum=digs[u]-'0';// 遍历该数字对应的所有字母for(inti=0;i<let[num].size();i++){// 直接在传参时进行字符串拼接，隐式完成了回溯的回退过程dfs(digs,strr+let[num][i],u+1);}}};