leetcode解题: Letter Combinations of a Phone Number (17)

发表于 | 分类于

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.

alt text

1
2
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：

先建一个map来存储每一个字母可以映射的字母，然后就是常规的backtracking的解法。没有特殊的地方。
C++

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
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        unordered_map<char, vector<char>> map;
        map['2'] = vector<char> {'a','b','c'};
        map['3'] = vector<char> {'d','e','f'};
        map['4'] = vector<char> {'g','h','i'};
        map['5'] = vector<char> {'j','k','l'};
        map['6'] = vector<char> {'m','n','o'};
        map['7'] = vector<char> {'p','q','r','s'};
        map['8'] = vector<char> {'t','u','v'};
        map['9'] = vector<char> {'w','x','y','z'};
        
        vector<string> res;
        string cur = "";
        if (digits.size() == 0) {
            return res;
        }
        helper(digits, 0, cur, res, map);
        return res;
        
        
    }
    
    void helper(string digits, int pos, string cur, vector<string>& res, unordered_map<char, vector<char>>& map) {
        if (cur.size() == digits.size()) {
            res.push_back(cur);
            return;
        }
        
        for (int i = pos; i < digits.size(); ++i) {
            char digit = digits[i];
            if (!map.count(digit)) {
                continue;
            } else {
                vector<char> dict = map[digit];
                for (int j = 0; j < dict.size(); ++j) {
                    string temp = cur + dict[j];
                    helper(digits, i + 1, temp, res, map);
                }
            }
        }
    }
};

Java

1