Cinte's Leetcode Record
0%

17. Letter Combinations of a Phone Number

Posted on Edited on In Disqus:
Symbols count in article: 2.4k Reading time ≈ 2 mins.

17. Letter Combinations of a Phone Number

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
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.size())
        {
            backtrack("", digits);
        }else
        {
            return {};
        }
    }

private:
    vector<string> ret;
    unordered_map<char, vector<char>> phone{{'2', {'a', 'b', 'c'}}, {'3', {'d', 'e', 'f'}}, {'4', {'g', 'h', 'i'}}, {'5', {'j', 'k', 'l'}}, {'6', {'m', 'n', 'o'}}, {'7', {'p', 'q', 'r', 's'}}, {'8', {'t', 'u', 'v'}}, {'9', {'w', 'x', 'y', 'z'}}};
    void backtrack(string comb, string digit)
    {
        if(!digit.size())
        {
            ret.push_back(comb);
        }

        for(auto& ch : phone[digit[0]])
        {
            backtrack(comb + ch, digit.substr(1));
        }
    }
};

review 

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
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty())
            return {};
        vector<string> ret;
        string tmp;
        backTrack(ret, tmp, digits, 0);
        return ret;
    }
private:
    unordered_map<int, vector<char>> map{
        {2, {'a', 'b', 'c'}},
        {3, {'d', 'e', 'f'}},
        {4, {'g', 'h', 'i'}},
        {5, {'j', 'k', 'l'}},
        {6, {'m', 'n', 'o'}},
        {7, {'p', 'q', 'r', 's'}},
        {8, {'t', 'u', 'v'}},
        {9, {'w', 'x', 'y', 'z'}}
        };
    void backTrack(vector<string>& ret, string& tmp, string& digits, int i)
    {
        if(i == digits.size())
        {
            ret.push_back(tmp);
            return;
        }
        for(auto& ch : map[digits[i] - '0'])
        {
            tmp += ch;
            backTrack(ret, tmp, digits, i + 1);
            tmp.pop_back();
        }
    }
};

还有一种

先把一个字母依次添加，然后再依次网上衔接各种情况