Well, a typical backtracking problem. Make sure you are clear with the following three problems:
Of course, remember to recover to the previous status once a partial solution is done. In the following code, line 18 (comb.resize(comb.length() - 1)) is for this purpose.
The following should be self-explanatory :)
1 class Solution { 2 public: 3 vector<string> letterCombinations(string digits) { 4 string mp[] = {" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; 5 vector<string> res; 6 if (digits.empty()) return res; 7 string comb; 8 combinations(digits, 0, mp, comb, res); 9 return res; 10 } 11 private: 12 void combinations(string& digits, int start, string mp[], string& comb, vector<string>& res) { 13 if (comb.length() == digits.length()) { 14 res.push_back(comb); 15 return; 16 } 17 for (int i = 0; i < (int)mp[digits[start] - ‘0‘].length(); i++) { 18 comb += (mp[digits[start] - ‘0‘][i]); 19 combinations(digits, start + 1, mp, comb, res); 20 comb.resize(comb.length() - 1); 21 } 22 } 23 };
Well, the above recursive backtracking solution is a typical solution. In fact, this problem can also be solved iteratively. Refer to this link for more information. I have rewritten the code below for your reference.
class Solution { public: vector<string> letterCombinations(string digits) { vector<string> res; if (digits.empty()) return res; string mp[] = {" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; res.push_back(""); for (int i = 0; i < (int)digits.length(); i++) { string letters = mp[digits[i] - ‘0‘]; vector<string> temp; for (int j = 0; j < (int)letters.length(); j++) for (int k = 0; k < (int)res.size(); k++) temp.push_back(res[k] + letters[j]); swap(res, temp); } return res; } };
[LeetCode] Letter Combinations of a Phone Number
原文：http://www.cnblogs.com/jcliBlogger/p/4582179.html