Letter Combinations of a Phone Number

由于这个月还没写博客,找道题应付下吧,主要原因是自己现在太忙了,得准备找工作啊,唉,弱的惨不忍睹。好吧,不抱怨了,进入正题,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”].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

其实就是组合问题,如下图所示:

如图所示,遍历完 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
#include <iostream>;
#include <vector>;
#include <string>;
using namespace std;
class Solution
{
public:
vector&lt;string&gt; letterCombinations(string digits)
{
int len = digits.size();
result.clear();
num[2] = &quot;abc&quot;;
num[3] = &quot;def&quot;;
num[4] = &quot;ghi&quot;;
num[5] = &quot;jkl&quot;;
num[6] = &quot;mno&quot;;
num[7] = &quot;pqrs&quot;;
num[8] = &quot;tuv&quot;;
num[9] = &quot;wxyz&quot;;
solve(digits,0,len);
return result;
}
void solve(string &amp;digits,int i,int len)
{
if(i == len)
{
str[len] = '&#92;&#48;';
string temp = str;
result.push_back(temp);
return;
}
unsigned int j;
int index = digits[i] - '0';
for(j = 0; j &lt; num[index].size(); j++)
{
str[i] = num[index][j];
solve(digits,i+1,len);
}
}
private:
vector&lt;string&gt; result;
string num[10];
char str[1000];
};
int main()
{
Solution solution;
string p;
p = &quot;23&quot;;
vector&lt;string&gt; p1;
p1 = solution.letterCombinations(p);
vector&lt;string&gt;::iterator iter;
for(iter=p1.begin();iter != p1.end();iter++)
{
cout&lt;&lt;*iter&lt;&lt;endl;
}
return 0;
}

最近开始集中精力做OJ了,唯一的感觉就是自己好弱,算法准备的有点晚了,有点找不上工作的节奏。算法也不是一朝一夕就能提高的,自己好好努力吧,即使实习拿不到dream offer,到正式找工作(9月份)还有时间努力,集中精力弥补自己弱点就可以了。