Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
47 lines (37 sloc) 1.65 KB
/*
Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.
1 2[abc] 3[def]
4[ghi] 5[jkl] 6[mno]
7[pgrs] 8[tuv] 9[wxyz]
Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
*/
/*
Hints:
当你遇到没法用循环解决的问题,那么它大概率是个递归问题。
很久没有写递归算法了,我决定好好写一篇文章来说说这个有趣的算法。
很多人觉得递归问题不好写,我觉得主要有两个原因:1.没有感受到这是个递归问题 2.不能清晰的知道到每次递归的状态
找一个你非常了解的递归模型去套就好了(像我习惯套 dfs 模型
对于这一题的话,输入的字符串的长度是不定的,所以我们需要通过递归把它变成一个-1的字符串
最后注意一下单字符的情况,也就是边界问题
*/
class Solution {
protected:
string number[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
vector<string> letterCombinations(string digits) {
vector<string> answer;
if (digits.length() > 0) {
vector<string> tmp = letterCombinations(digits.substr(1, digits.length() - 1));
if(tmp.size()==0) tmp.push_back("");
for(int i=0;i<number[digits[0]-'0'].length();i++)
for(int j=0;j<tmp.size();j++){
string s = number[digits[0]-'0'][i]+tmp[j];
answer.push_back(s);
}
}
return answer;
}
};