Monday, December 24, 2012

[LeetCode] Letter Combinations of a Phone Number 解题报告


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 problem

[解题思路]
经典递归题。

[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:

andy said...
This comment has been removed by the author.
andy said...

请问这个解法的时间复杂度怎么分析?谢谢!

Logan L Watson said...

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