电话号码的字母组合，是大家熟悉的字母九宫格键盘，按照题目要求尽可能的按照字母排序；
所有的数据盘排列和下图大致相当；
解题思想是：
相邻的两个数字中，第一个数字所包含的字母是根节点，第二个数字包含的字母自动分配到每个根节点上，按照这种思想，我们只需要处理相邻两个数字，对每个根节点进行扩展，得到所有想要的组合；
class Solution { public: //手机上每个数字对应的字母 vector<string> numTostring(char n) { vector<string> ans; switch (n) { case '2': ans = { "a","b","c" }; break; case '3': ans = { "d","e","f" }; break; case '4': ans = { "g","h","i" }; break; case '5': ans = { "j","k","l" }; break; case '6': ans = { "m","n","o" }; break; case '7': ans = { "p","q","r", "s" }; break; case '8': ans = {"t","u","v"}; break; case '9': ans = { "w","x","y","z" }; break; } return ans; } //相邻数字所代表的所有字母组合种类 vector<string> Ins(char n, vector<string>m) { vector<string> ans; int cnt = 0; auto s = numTostring(n); if (m.empty()) { for (auto i = s.begin(); i != s.end(); i++, cnt++) { ans.push_back(*i); } } else { for (auto i = m.begin(); i != m.end(); i++) { for (auto j = s.begin(); j != s.end(); j++) { ans.push_back(*i + *j); } } } return ans; } //字母组合的主干 vector<string> letterCombinations(string digits) { vector<string> ss; for (auto i = digits.begin(); i!= digits.end(); i++) { ss=Ins(*i, ss); } sort(ss.begin(), ss.end()); return ss; } };
