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
63
#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月份）还有时间努力，集中精力弥补自己弱点就可以了。