由于这个月还没写博客，找道题应付下吧，主要原因是自己现在太忙了，得准备找工作啊，唉，弱的惨不忍睹。好吧，不抱怨了，进入正题，LeetCode 上面的一道题，题目描述为：
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”].其实就是组合问题，如下图所示：
如图所示，遍历完 1，2，3，就把a,d (g,h,i)遍历完了，之后回溯到e，就是个DFS搞定。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
using namespace std;
class Solution
{
public:
vector<string > letterCombinations(string digits)
{
int len = digits.size();
result .clear();
num[2 ] = "abc";
num[3 ] = "def";
num[4 ] = "ghi";
num[5 ] = "jkl";
num[6 ] = "mno";
num[7 ] = "pqrs";
num[8 ] = "tuv";
num[9 ] = "wxyz";
solve(digits,0 ,len);
return result ;
}
void solve(string &digits;,int i,int len)
{
if (i == len)
{
str[len] = '&
string temp = str;
result .push_back(temp);
return ;
}
unsigned int j;
int index = digits[i] - '0 ';
for (j = 0 ; j < num[index].size(); j++)
{
str[i] = num[index][j];
solve(digits,i+1 ,len);
}
}
private:
vector<string > result ;
string num[10 ];
char str[1000 ];
};
int main()
{
Solution solution;
string p;
p = "23 ";
vector<string > p1;
p1 = solution.letterCombinations(p);
vector<string >::iterator iter;
for (iter=p1.begin();iter != p1.end ();iter++)
{
cout<<*iter<
}
return 0 ;
}
最近开始集中精力做OJ了，唯一的感觉就是自己好弱，算法准备的有点晚了，有点找不上工作的节奏。算法也不是一朝一夕就能提高的，自己好好努力吧，即使实习拿不到dream offer，到正式找工作（9月份）还有时间努力，集中精力弥补自己弱点就可以了。
