Leetcode刷题详解——电话号码的字母组合
1. 题目链接：17. 电话号码的字母组合
2. 题目描述：
给定一个仅包含数字
2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]示例 2：
输入：digits = "" 输出：[]示例 3：
输入：digits = "2" 输出：["a","b","c"]提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
3. 解法：
3.1 算法思路：
每个位置可以选择的字符与其他位置并不冲突，因此不需要标记已经出现的字符，只需要将每个数字依次填入字符串中进行递归，在回溯是撤销填入操作即可
在递归之前我们需要定义一个的字典 hash，纪录2~9各自对应的字符
3.2 递归函数流程：
- 递归结束条件时：当
pos等于digits的长度时，将path加入到ret中返回 - 取出当前处理的数字
digits，根据hash取出的对应的字母列表letters - 遍历字母列表
letters，将当前字母加入到组合字符串path的末尾，然后递归处理下一个数字（传入pos+1，表示处理下一个数字） - 递归处理结束后，将加入的字母从
path的末尾删除，表示回溯 - 最终返回
ret即可
3.3 C++算法代码：
class Solution {string hash[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; // 定义一个字符串数组，存储每个数字对应的字母组合string path; // 定义一个字符串变量，存储当前生成的字母组合vector<string> ret; // 定义一个字符串向量，存储所有可能的字母组合结果
public:vector<string> letterCombinations(string digits) { // 定义一个公共成员函数，接受一个字符串参数digits，表示输入的数字序列if(digits.size()==0) return ret; // 如果输入的数字序列为空，则直接返回空的结果向量retdfs(digits,0); // 否则，调用dfs函数进行深度优先搜索return ret; // 返回结果向量ret}void dfs(string& digits,int pos) // 定义一个私有成员函数dfs，接受两个参数：一个是输入的数字序列digits，另一个是当前处理的位置pos{if(pos==digits.size()) // 如果当前位置等于数字序列的长度{ret.push_back(path); // 将当前的字母组合添加到结果向量ret中return; // 返回}for(auto ch:hash[digits[pos]-'0']) // 遍历当前数字对应的字母组合{path.push_back(ch); // 将字母添加到path中dfs(digits,pos+1); // 递归地调用dfs函数处理下一个位置的数字path.pop_back(); // 将最后一个添加的字母从path中移除}}
};