首页 > 代码库 > Letter Combinations of a Phone Number(带for循环的DFS，递归总结)
Letter Combinations of a Phone Number(带for循环的DFS，递归总结)
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23"Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
又加深了对DFS的认识，在递归函数中，需要把握几个点，总能各个击破。
1.就是变化的量要作为参数来传递，这样也就是每个函数在自己的栈中都有该局部变量，这样就可以在回溯到某个点的时候，他的局部变量不会消失。
2.一般的终止条件中，计算结果
代码：
private: map<char, vector<char> > dict; vector<string> ret; int len;public: void createDict() { dict.clear(); dict[‘2‘].push_back(‘a‘); dict[‘2‘].push_back(‘b‘); dict[‘2‘].push_back(‘c‘); dict[‘3‘].push_back(‘d‘); dict[‘3‘].push_back(‘e‘); dict[‘3‘].push_back(‘f‘); dict[‘4‘].push_back(‘g‘); dict[‘4‘].push_back(‘h‘); dict[‘4‘].push_back(‘i‘); dict[‘5‘].push_back(‘j‘); dict[‘5‘].push_back(‘k‘); dict[‘5‘].push_back(‘l‘); dict[‘6‘].push_back(‘m‘); dict[‘6‘].push_back(‘n‘); dict[‘6‘].push_back(‘o‘); dict[‘7‘].push_back(‘p‘); dict[‘7‘].push_back(‘q‘); dict[‘7‘].push_back(‘r‘); dict[‘7‘].push_back(‘s‘); dict[‘8‘].push_back(‘t‘); dict[‘8‘].push_back(‘u‘); dict[‘8‘].push_back(‘v‘); dict[‘9‘].push_back(‘w‘); dict[‘9‘].push_back(‘x‘); dict[‘9‘].push_back(‘y‘); dict[‘9‘].push_back(‘z‘); } void dfs(int loc,string digits,string temp) { if(loc==len){ ret.push_back(temp); //temp.erase(temp.size()-1);在这里擦除是没有用的，这已经是下一个递归函数，回溯到上一个的时候，它的局部变量temp还是三个字母 return; } for (int i=0;i<dict[digits[loc]].size();++i) { temp.push_back(dict[digits[loc]][i]); dfs(loc+1,digits,temp); temp.erase(temp.size()-1); } } vector<string> letterCombinations(string digits) { createDict(); vector<string> tempres; tempres.push_back(""); if(digits.empty()) return tempres; len=digits.size(); dfs(0,digits,""); return ret; }};int main(){ //freopen("C:\\Users\\Administrator\\Desktop\\a.txt","r",stdin); Solution so; so.letterCombinations("258"); return 0;}
Letter Combinations of a Phone Number(带for循环的DFS，递归总结)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。