写法一写法二写法三写法四写法五

写法一：

这种方法只能击败1%，但是经过小小的优化，性能有了很大的提高。

class Solution { public: vector<string> rel; string tmp; int d_len; char d[10][5] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; void findCombination(string a, int stt, string in_data) { if(stt == d_len) { rel.push_back(tmp); return; } for(int i = 0; i < strlen(d[in_data[stt] - '0']); i++) { string tmp2 = tmp; tmp += d[in_data[stt] - '0'][i]; findCombination(tmp, stt + 1, in_data); tmp = tmp2; // d[in_data[i] - '0'][j]; } } vector<string> letterCombinations(string digits) { d_len = digits.length(); if(!d_len) return rel; findCombination(tmp, 0, digits); return rel; } };

写法二：

函数调用计算字符串长度写到循环外。这种写法击败了40%。

class Solution { public: vector<string> rel; string tmp; int d_len; char d[10][5] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; void findCombination(string a, int stt, string in_data) { if(stt == d_len) { rel.push_back(tmp); return; } int di_len = strlen(d[in_data[stt] - '0']); for(int i = 0; i < di_len; i++) { string tmp2 = tmp; tmp += d[in_data[stt] - '0'][i]; findCombination(tmp, stt + 1, in_data); tmp = tmp2; // d[in_data[i] - '0'][j]; } } vector<string> letterCombinations(string digits) { d_len = digits.length(); if(!d_len) return rel; findCombination(tmp, 0, digits); return rel; } };

写法三：

使用string的push_back和pop_back来操作，发现和速度特别慢。

class Solution { public: vector<string> rel; string tmp; int d_len; char d[10][5] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; void findCombination(string a, int stt, string in_data) { if(stt == d_len) { rel.push_back(tmp); return; } int di_len = strlen(d[in_data[stt] - '0']); for(int i = 0; i < di_len; i++) { // string tmp2 = tmp; tmp.push_back(d[in_data[stt] - '0'][i]); // += d[in_data[stt] - '0'][i]; findCombination(tmp, stt + 1, in_data); tmp.pop_back(); //tmp = tmp2; // d[in_data[i] - '0'][j]; } } vector<string> letterCombinations(string digits) { d_len = digits.length(); if(!d_len) return rel; findCombination(tmp, 0, digits); return rel; } };

写法四：

不使用全局变量进行一次计算。

class Solution { public: void findCombination(string tmp, const char d[10][5], string &in_data, vector<string> &rel) { int stt = tmp.size(); if(stt == in_data.size()) { rel.push_back(tmp); return; } int di_len = strlen(d[in_data[stt] - '0']); for(int i = 0; i < di_len; i++) { string tmp2 = tmp; tmp += d[in_data[stt] - '0'][i]; findCombination(tmp, d, in_data, rel); tmp = tmp2; // d[in_data[i] - '0'][j]; } } vector<string> letterCombinations(string digits) { vector<string> rel; string tmp; int d_len; const char d[10][5] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; d_len = digits.length(); if(!d_len) return rel; findCombination(tmp, d, digits, rel); return rel; } };

http://www.cnblogs.com/longdouhzt/archive/2012/04/22/2465399.html https://zhidao.baidu.com/question/1669208534797631547.html http://blog.csdn.net/yunyun1886358/article/details/5659851

写法五

直接使用一个函数，而不需要分开来写。但是还是分开两个函数来做显得更加简洁。

class Solution { public: const char d[10][5] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; string tmp; vector<string> rel; vector<string> letterCombinations(string digits) { int d_len; d_len = digits.length(); if(!d_len) { if(tmp.empty()) return rel; rel.push_back(tmp); return rel; } int row = digits[0] - '0'; int r_len = strlen(d[row]); for(int i = 0; i < r_len; i++) { tmp.push_back(d[row][i]); if(d_len > 0) rel = letterCombinations(digits.substr(1)); tmp.pop_back(); } return rel; } }; class Solution { public: string num2alpha[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; vector<string> letterCombinations(string digits) { vector<string> result; if(digits.empty()) return result; char curDigit = digits[0]; string curStr = num2alpha[curDigit-'2']; vector<string> subResult = letterCombinations(digits.substr(1)); if(subResult.empty()) subResult.emplace_back(""); for(int i = 0; i < curStr.length(); ++i) { for(int j = 0; j < subResult.size(); ++j) { string tmp = ""; tmp += curStr[i]; tmp = tmp + subResult[j]; result.emplace_back(tmp); } } return result; } }