当前位置 博文首页 > Letter Combinations of a Phone Number_让代码改变世界：LeetCo
快中秋节了，心情不佳，多写几道吧，只有编程能带给我片刻的宁静啊。。。
今天给大家讲一下第17题，难度为中等，这个题目考察的到不是什么高深的算法，考的是对编程技巧的掌握吧，对语言应用方面要求多余算法设计的要求。题目的背景挺有意思，一起来看一下
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"].这个题目对于玩儿过手机的人都不存在理解问题，尤其是使用过汉语拼音的同学，机器是如何通过8个有效按键来匹配各种可能的拼音输入的呢？我们可以想见，肯定是先找出所有的组合，然后从中去除没有意义的，我们这次要做的比较简单，就是找出所有的组合，并不用对其意义进行验证。
首先的思路是要建立一个对照表，这个就不用多说了吧，你得把数字键和字母的对照规律“告诉”程序啊。然后就是对digit进行一个一个分解组合了，说白了就是一个全组合问题，可以把每个数字对应的字母看做一个包，有多少字母就有多少包，然后就是从每个包里往外拿一个字母，每个包拿且只拿一个，把所有可能拿到的结果放到一个容器了就可以了。
程序难点主要在于digit的长度事先不知道，所以不能用多个循环的“蛮力法”解决，因为你不知道要写多少个循环体嘛。
对付这种题有很多思路，比如迭代法和减一法。迭代是大神的事情，我们采用减一法来试一下，通过分析我们可以发现，每加入一个数字时，组合的方式都是两个容器的两两配对问题了，所以我们可以自底向上的先从一个数字开始，然后逐个将数字加入生成不同的组合，在这个过程中我们要解决的就是配对问题和组合容器更新问题，这两个问题都比较简单，是可以解决的。于是就有了如下代码：
vector<string> add_string_to_vecString(vector<string> &vstr,const string &s)
{
vector<string> result;
size_t vs_len=vstr.size();size_t s_len=s.size();
if(vs_len==0&&s_len==0)return result;
string temp;
if(vs_len==0&&s_len!=0)
{
for(size_t i=0;i<s_len;++i)
{ temp.clear();
temp.push_back(s[i]);
result.push_back(temp);
}
return result;
}
if(vs_len!=0&&s_len==0)return vstr;
result.resize(vstr.size()*s.size());
if(vstr.size()==0&&s.size()==0)result.push_back(s);
for(int i=0;i<vstr.size();++i)
{
for(int j=0;j<s.size();++j)
{
result[i*s.size()+j]=vstr[i];
result[i*s.size()+j].push_back(s[j]);
}
}
return result;
}
class Solution {
public:
vector<string> letterCombinations(string digits) {
//构造对照表
vector<string> vstr;
vstr.push_back("abc");
vstr.push_back("def");
vstr.push_back("ghi");
vstr.push_back("jkl");
vstr.push_back("mno");
vstr.push_back("pqrs");
vstr.push_back("tuv");
vstr.push_back("wxyz");
size_t len = digits.size();
vector<string> result;
for(size_t i=0;i<len;++i)
{
size_t index=digits[i]-'0'-2;//数字字符转数字
result = add_string_to_vecString(result,vstr[index]);
}
return result;
}
};里面部分语句可以改的更漂亮些，但这样程序的可读性会有所降低，个人认为这样的代码可读性还是可以的，程序的运行时间为0ms，呵呵，应该是输入的实例比较少，所以时间太短没法统计了吧，总之代码的质量还算过关的，所以也就没有再找别的大神们的代码。
其实代码的思路主要还是迭代的思想，不过用循环的方式实现了而已，因为题目自身有迭代的性质，但迭代代码编写比较难，这里也就不深挖了，有兴趣的同学可以试一下。
总之，建立对照表，想到减一法的自底向上设计方法是本题的关键。所以还是那句话，要想做一个合格的程序员，算法课程是不能少的，大家多多努力吧。
预祝大家中秋快乐，祝每个坚持的人都能实现自己的梦想!!!
