[17] 电话号码的字母组合 题目描述难度 中等标签数组哈希表回溯给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。示例 1输入digits “23”输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]示例 2输入digits “2”输出[“a”,“b”,“c”] 解题思路使用一个哈希表存储键盘上的每个字符,然后用一个dfs去逐个回溯遍历digits里面的每个字符 代码实现classSolution{public:// 主函数输入数字字符串 digits返回所有可能的字母组合vectorstringletterCombinations(string digits){// 1. 建立 数字 - 字母 的映射表电话键盘unordered_mapchar,stringmp;mp[2]abc;mp[3]def;mp[4]ghi;mp[5]jkl;mp[6]mno;mp[7]pqrs;mp[8]tuv;mp[9]wxyz;// 2. 定义结果集保存所有最终的字母组合vectorstringres;// 3. 定义当前正在拼接的字符串string str;// 4. 开始递归回溯你写的bfs其实是dfs回溯dfs(digits,mp,res,str);returnres;}// 递归回溯函数// digits当前还没处理完的数字串// mp数字字母映射表// res结果集// str当前拼接的字符串voiddfs(stringdigits,unordered_mapchar,stringmp,vectorstringres,stringstr){// 递归终止条件// 如果 digits 为空说明所有数字都处理完了// 当前 str 就是一个完整组合存入结果集if(digits.empty()){res.emplace_back(str);return;}// 遍历当前第一个数字对应的所有字母// 比如 digits[0] 2就遍历 a,b,cfor(inti0;imp[digits[0]].size();i){// 取出当前要拼接的字母charchmp[digits[0]][i];// 做选择 // 把字母拼接到当前字符串strstrch;// 截取去掉第一个数字后的新数字串继续递归string digits1digits.substr(1);bfs(digits1,mp,res,str);// 回溯撤销选择// 删掉最后一个字母回到上一步状态尝试下一个字母str.pop_back();}}}; 复杂度分析digits里面的数字有3或4两种长度,若两种长度的数字个数分别为n和m,由于回溯会遍历所有组合,所以总时间复杂度为:时间复杂度O(3n∗4m)O(3^n*4^m)O(3n∗4m)空间复杂度O(n)日期2026-5-7