leetcode17. 电话号码的字母组合，dfs深度优先搜索
leetcode17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：
输入：digits = “”
输出：[]
示例 3：
输入：digits = “2”
输出：[“a”,“b”,“c”]
算法思想
算法步骤
1.初始化：创建一个结果列表res，用于存储所有可能的字母组合；path用于存储当前的字母组合；a是一个数组，存储每个数字键对应的所有可能的字母。
2.递归函数dfs：这是一个深度优先搜索（DFS）的递归函数，用于生成所有可能的字母组合。
参数： n：输入数字字符串的长度。 t：当前处理到的数字键的索引。 digits：输入的数字字符串。
递归终止条件：当t等于n时，说明已经处理完所有的数字键，将当前的path添加到结果列表res中。 递归逻辑：
计算当前数字键对应的字母数组a[digits[t]-‘2’]的大小。 遍历这个字母数组，对于每个字母：
如果是第一个数字键（t==0），则将字母赋值给path；否则，将字母追加到path的末尾。 递归调用dfs，将t加1，继续处理下一个数字键。
回溯，移除path末尾的字母，撤销上一步的操作。
3.主函数letterCombinations：这是对外提供的接口函数，接收一个数字字符串digits作为输入，调用dfs函数，并返回所有可能的字母组合。
算法流程
具体代码
class Solution {
public:vector<string> res;string path;string a[8]={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};void dfs(int n,int t,string digits) //1 0{if(t==n) {res.push_back(path);return ;}int size=a[digits[t]-'2'].size();for(int i=0;i<size;i++){path+=a[digits[t]-'2'][i];dfs(n,t+1,digits);path.erase(path.end()-1);}}vector<string> letterCombinations(string digits) {if(digits=="") return res;int n=digits.size();dfs(n,0,digits);return res;}
};