首页 > 代码库 > LeetCode: LetterCombinations 题解
LeetCode: LetterCombinations 题解
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.
题解： 递归。首先将输入字符串解析成数字集合，记录字符串大小为Len。
生成的字符串长度依旧为Len。从首位开始判断该位可以填充的字符。
注意：本题首先需要对手机键盘的字符进行映射，作为辅助。
1 class Solution { 2 public: 3 char vi[10][4]; 4 vector<string > out; 5 int length; 6 void getVi() 7 { 8 int i,j; 9 for(i=0;i<=9;i++)10 for(j=0;j<4;j++)11 vi[i][j]=0;12 for(i=2;i<=7;i++)13 {14 for(j=0;j<3;j++)15 {16 vi[i][j]= ‘a‘+ 3*(i-2)+j;17 }18 }19 vi[0][0]=‘ ‘;20 vi[7][3]=‘s‘;21 for(i=8;i<=9;i++)22 {23 for(j=0;j<3;j++)24 {25 vi[i][j]= ‘b‘ + 3*(i-2)+j;26 }27 }28 vi[9][3]=‘z‘;29 }30 31 void DFS(int len,string digits, string c)32 {33 if(len==length)34 {35 out.push_back(c);36 return ;37 }38 int count = digits[len]-‘0‘;39 for(int i=0;i<4;i++)40 {41 if(vi[count][i]!=0)42 DFS(len+1,digits,c+vi[count][i]);43 }44 }45 vector<string> letterCombinations(string digits) {46 out.clear();47 length = digits.size();48 if(length==0) 49 {50 out.push_back("");51 return out;52 }53 if(digits.find(‘1‘)!=string::npos) return out;54 getVi();55 DFS(0,digits,"");56 return out;57 }58 };
转载请注明出处： http://www.cnblogs.com/double-win/ 谢谢！
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。