当前位置：首页 > news >正文

17 电话号码的字母组合

news 2026/5/8 8:29:30

[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，返回所有可能的字母组合vector<string>letterCombinations(string digits){// 1. 建立 数字 -> 字母 的映射表（电话键盘）unordered_map<char,string>mp;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. 定义结果集，保存所有最终的字母组合vector<string>res;// 3. 定义当前正在拼接的字符串string str;// 4. 开始递归回溯（你写的bfs其实是dfs回溯）dfs(digits,mp,res,str);returnres;}// 递归回溯函数：// digits：当前还没处理完的数字串// mp：数字字母映射表// res：结果集// str：当前拼接的字符串voiddfs(string&digits,unordered_map<char,string>&mp,vector<string>&res,string&str){// 递归终止条件：// 如果 digits 为空，说明所有数字都处理完了// 当前 str 就是一个完整组合，存入结果集if(digits.empty()){res.emplace_back(str);return;}// 遍历当前第一个数字对应的所有字母// 比如 digits[0] = '2'，就遍历 a,b,cfor(inti=0;i<mp[digits[0]].size();i++){// 取出当前要拼接的字母charch=mp[digits[0]][i];// ==================== 做选择 ====================// 把字母拼接到当前字符串str=str+ch;// 截取去掉第一个数字后的新数字串，继续递归string digits1=digits.substr(1);bfs(digits1,mp,res,str);// ==================== 回溯（撤销选择）====================// 删掉最后一个字母，回到上一步状态，尝试下一个字母str.pop_back();}}};