Letter Combinations

发表于 | 分类于

Letter Combinations

题目描述：

给定手机键盘上的数字字符的字符串，要求输出所有可能由该数字字符串得到英文字符串。

例子：

具体描述看LeetCode17

解题思路：

主要的思路是递归的方式。我们针对每一位的数字字符进行遍历，然后不断递归到下一层得到字符串的组合。其中需要注意的是我们每次加上字符后需要回溯一步。

代码如下：

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
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        string str;
        vector<string> res;
        map<char, vector<char>> hash;
        if (digits == "") return res;
        hash.insert({'2',{'a', 'b', 'c'}});
        hash.insert({'3',{'d', 'e', 'f'}});
        hash.insert({'4',{'g', 'h', 'i'}});
        hash.insert({'5',{'j', 'k', 'l'}});
        hash.insert({'6',{'m', 'n', 'o'}});
        hash.insert({'7',{'p', 'q', 'r', 's'}});
        hash.insert({'8',{'t', 'u', 'v'}});
        hash.insert({'9',{'w', 'x', 'y', 'z'}});
        hash.insert({'0',{' '}});
        //构建各个数字对应字符的哈希表
        permutation(res, str, hash, 0, digits.size(), digits);
        //调用递归函数来得到所有的组合
        //其中res是保存组合结果；str是当前的组合结果；
        //begin和end表示要找到源字符begin到end的位置的所有组合字符
        return res;
        
    }
    void permutation(vector<string>& res, string& str, map<char, vector<char>>& hash, int begin, int end, string digits){
        if (begin >= end){
            res.push_back(str);
            return;
            //begin大于等于end的情况说明到达尾部，将结果保存即可
        }
        for (int i = 0; i < hash[digits[begin]].size(); i++){
        //对当前的begin位置的所有可能进行遍历
            str = str + hash[digits[begin]][i];
            //将每种可能加到str字符串上
            permutation(res, str, hash, begin + 1, end, digits);
            //进行下一层的遍历，注意此时的begin加1
            str.pop_back();
            //另外需要回溯一步
        }
    }
};