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.
» Solve this problemAlthough the above answer is in lexicographical order, your answer could be in any order you want.
[解题思路]
经典递归题。
[Code]
1: vector<string> letterCombinations(string digits) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: string trans[] = {"", " ", "abc", "def", "ghi", "jkl",
5: "mno", "pqrs", "tuv", "wxyz"};
6: vector<string> set;
7: string seq;
8: Generater(trans, digits, 0, seq, set);
9: return set;
10: }
11: void Generater(string trans[], string& digits,
12: int deep, string& result, vector<string>& set)
13: {
14: if(deep == digits.size())
15: {
16: set.push_back(result);
17: return;
18: }
19: int curDig = digits[deep] - 48;
20: for(int i =0; i < trans[curDig].size(); i++)
21: {
22: result.push_back(trans[curDig][i]);
23: Generater(trans, digits, deep+1, result, set);
24: result.resize(result.size() -1);
25: }
26: }
[注意]
1. Line 19。ACSII码转int要减去48.
3 comments:
请问这个解法的时间复杂度怎么分析?谢谢!
Thanks so much for this information. I have to let you know I concur on several of the points you make here and others may require some further review, but I can see your viewpoint. Benjamin Luker
Post a Comment