LeetCode之Letter Combinations of a Phone Number

本文主要是介绍LeetCode之Letter Combinations of a Phone Number，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*方法一：迭代求解法。这里类似于模拟，每次考虑添加数字对应的字母，当字母的
个数n大于1时，需要给结果中增加n-1个string，以作为结果。*/
class Solution {
public:vector<string> letterCombinations(string digits) {string digit_strings[10] = {" ", " ", "abc", "def", "ghi","jkl", "mno", "pqrs", "tuv", "wxyz"};vector<string> res;if(digits.empty()) return res;res.push_back(string(""));for(int i = 0; i < digits.size(); ++i){int size = res.size();for(int n = 0; n < size; ++n){for(int j = 1; j < digit_strings[digits[i]-'0'].size(); ++j){res.push_back(res[n]);res[res.size()-1] += digit_strings[digits[i]-'0'][j];}res[n] += digit_strings[digits[i]-'0'][0];}}return res;}
};/*方法二：递归法。采用深度搜索的方法，对当前的字母进行选择，然后再递归求解子数组的
combinations。*/
class Solution {
public:vector<string> letterCombinations(string digits) {vector<string> res;if(digits.empty()) return res;string path;letterCombinations(digits, res, path, 0);return res;}void letterCombinations(const string &digits, vector<string> &res, string &path, int cur){string digit_strings[10] = {" ", " ", "abc", "def", "ghi","jkl", "mno", "pqrs", "tuv", "wxyz"};if(cur == digits.size()){res.push_back(path);return;}for(int i = 0; i < digit_strings[digits[cur]-'0'].size(); ++i){path += digit_strings[digits[cur]-'0'][i];letterCombinations(digits, res, path, cur+1);path.pop_back();}}
};

这篇关于LeetCode之Letter Combinations of a Phone Number的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---