Letter Combinations of a Phone Number--LeetCode

1.题目

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.

2.题意

给定一个数字字符串, 返回该数字可以表示的所有可能的字母组合 下面给出了数字到字母的映射 (就像在电话按钮上一样) string dict[] = {“abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz”}; 注意: 虽然上面的答案是字典的, 但你的答案可能是你想要的任何顺序

3.分析

排列组合问题 1）递归版 建立字典保存每个数字所代表的字符串 用一个变量level，记录当前生成的字符串的字符个数 递归出口为level == digits.size() 注意letterCombinationsDFS(result, dict, digits, level + 1, temp); 不要写成letterCombinationsDFS(result, dict, digits, level + 1, str); level == digits.size()之后result.push_back(temp);再return;不要写成return result;

2）迭代版 依次读取数字 将数字可以代表的字符加入当前结果 然后进入下一次迭代 注意提前result.push_back(“”); string temp = result.front();不要写成string temp = result.begin(); 不要忘记return reuslt;

4.代码

1）递归版

class Solution { public: vector<string> letterCombinations(string digits) { vector<string> result; if(digits.size() == 0) return result; string dict[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; letterCombinationsDFS(result, dict, digits, 0, ""); return result; } void letterCombinationsDFS(vector<string> &result, string dict[], string digits, int level, string temp) { if(level == digits.size()) { result.push_back(temp); return; } string str = dict[digits[level] - '2']; for(int i = 0; i < str.size(); ++i) { temp.push_back(str[i]); letterCombinationsDFS(result, dict, digits, level + 1, temp); temp.pop_back(); } return; } };

2）迭代版

class Solution { public: vector<string> letterCombinations(string digits) { vector<string> result; if(digits.size() == 0) return result; string dict[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; result.push_back(""); for(int i = 0; i < digits.size(); ++i) { int n = result.size(); string str = dict[digits[i] - '2']; for(int j = 0; j < n; ++j) { string temp = result.front(); result.erase(result.begin()); for(int k = 0; k < str.size(); ++k) { result.push_back(temp + str[k]); } } } return result; } };