力扣17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
可视化
a b c
d e f d e f d e f
示例 2：
输入：digits = "" 输出：[]
示例 3：
输入：digits = "2" 输出：["a","b","c"]
代码：
/* 构建多叉树，每个结点有3或4个子节点。 以digits = “23” 为例 第一个数字为2 对于字母 a b c，于是构建3颗分别以a b c为头的树 之后遍历剩余数字，如3，将3对应字母 d e f分别插入每一颗树的 每一个叶子 结点后 a b c d e f d e f d e f 之后dfs每条颗树的每条路径，加入到ans */ struct tree{ char c; vector<tree*>next; tree(char cc):c(cc){} }; void insert(tree * t,string s){ //将一棵树的每个叶结点都插入s中的字母结点 if(t == NULL) return; //写不写都行，初始时t肯定不空，子递归的终止条件也不是这个。 if(t->next.size() == 0){ //如果是叶子结点，将s的每一个字符插入子节点 for(char c : s){ tree * tmp = new tree(c); t->next.push_back(tmp); } return; } for(int i = 0; i < t->next.size(); i++){ //也是dfs遍历每一个叶子结点 insert(t->next[i],s); } } void push(vector<string>&ans,string tmp,tree * t){ //dfs多叉树 if(t->next.size() == 0){ tmp+=t->c; ans.push_back(tmp); return; } tmp+=t->c; for(int i = 0; i < t->next.size(); i++){ //因为参数传值，不是引用，所以不需要专门处理回溯，如果传引用，要将tmp+=t->c写到push上一行，在push下一在去掉最后一个字母。 push(ans,tmp,t->next[i]); } } class Solution { public: vector<string> letterCombinations(string digits) { if(digits.size() == 0) return {}; vector<string> zimu{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; //下标对应号码 char one =digits[0]; //取第一个数字，构建对应字母为头的树 3颗或4颗 vector<tree*> first(zimu[one-'0'].size(),NULL); //将根节点放在数组 for(int i = 0; i < zimu[one-'0'].size(); i++){ //初始化每棵树的根结点字母 first[i] = new tree(zimu[one-'0'][i]); } for(int i = 1; i < digits.size(); i++){ //处理剩余号码 for(int j = 0; j < first.size(); j++){ //每棵树都insert 某号码对应的个字母 insert(first[j],zimu[digits[i]-'0']); } } vector<string>ans; string tmp = ""; for(int i = 0; i < first.size(); i++){ push(ans,tmp,first[i]); //every tree path } return ans; } };