【Hot 100 刷题计划】 LeetCode 17. 电话号码的字母组合 | C++ 回溯算法经典模板

张开发
• 2026/4/10 1:45:12 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【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;vectorstringres;// 巧妙设计下标直接对应数字0和1为空vectorstringlet{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};vectorstringletterCombinations(string digits){ndigits.size();// 唯一需要注意的致命陷阱特判空字符串if(n0)returnres;string str;dfs(digits,str,0);returnres;}voiddfs(string digs,string strr,intu){// 递归终止条件当前组合的长度等于输入的数字长度if(strr.size()digs.size()){res.push_back(strr);return;}// 利用直接映射获取当前数字intnumdigs[u]-0;// 遍历该数字对应的所有字母for(inti0;ilet[num].size();i){// 直接在传参时进行字符串拼接隐式完成了回溯的回退过程dfs(digs,strrlet[num][i],u1);}}};

更多文章