Letter Combinations of a Phone Number
LeetCode笔记 阅读(470)
编号 : 17 难度 : <font color="orange">Medium</font> # 题目 : >Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters. > > > >**Example**: > >>**Input**: "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. # 解 : ```Cpp class Solution { public: vector<string> letterCombinations(string digits) { /* 按键对应字符串的映射 */ map<char, string> dict = { {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}, }; /* 最终结果 */ vector<string> ret; if(digits.size() != 0 && digits.find_first_not_of("23456789") == string::npos) { ret.push_back(""); // 作为root } else { return ret; // 输入不合法 } /* 缓存中间过程 */ vector<string> temp; for(auto& key : digits) { temp.clear(); for(auto& ch : dict[key]) { for(auto& str : ret) { temp.push_back(str + ch); } } ret = temp; } return ret; } }; ``` # 分析 : 这道题是一个很简单的多层循环嵌套,难点在于嵌套的层数是运行时得到的,所以不能依靠编码完成循环。 这题是一个树形结构,设输入为 "23",则有 : ``` 2 a b c / | \ / | \ / | \ 3 ad ae af bd be bf cd ce cf ``` 为了实现上述过程,用一个动态数组(A)保存输入完成一个按键的结果,嵌套遍历下一个按键上的字符和该数组,过程中用另一个动态数组(B)做缓存,遍历完成之后将B赋值给A然后清空B,再输入下一个按键。 在上面的代码中,为了让循环可以正常展开,预先在结果里插入了一个空字符串,相当于树的根 : ``` (空字符串作为树根) / | \ 2 a b c / | \ / | \ / | \ 3 ad ae af bd be bf cd ce cf ```