题目介绍
Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.
Example:
1 | Input: "23" |
2 | 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.
给一串由2-9组成的字符串，每个数字对应9键手机的字母表。返回可能生成的所有字符串
排列顺序任意
解
1 | class Solution { |
2 | private: |
3 | void help(string& digits, unordered_map<char, string>& phoneMap, vector<string>& ret, string tmp, int i) { |
4 | if (i == digits.size()) { |
5 | ret.emplace_back(tmp); |
6 | return; |
7 | } |
8 | char c = digits[i]; |
9 | string letter = phoneMap[c]; |
10 | for (int j = 0; j < letter.size(); j++) { |
11 | help(digits, phoneMap, ret, tmp+letter[j], i+1); |
12 | } |
13 | } |
14 | public: |
15 | vector<string> letterCombinations(string digits) { |
16 | vector<string> ret; |
17 | if (digits.size() == 0) { |
18 | return ret; |
19 | } |
20 | unordered_map<char, string> phoneMap; |
21 | phoneMap['2'] = "abc"; |
22 | phoneMap['3'] = "def"; |
23 | phoneMap['4'] = "ghi"; |
24 | phoneMap['5'] = "jkl"; |
25 | phoneMap['6'] = "mno"; |
26 | phoneMap['7'] = "pqrs"; |
27 | phoneMap['8'] = "tuv"; |
28 | phoneMap['9'] = "wxyz"; |
29 | help(digits, phoneMap, ret, "", 0); |
30 | return ret; |
31 | } |
32 | }; |
Runtime: 0 ms
Memory Usage: 8.6 MB
内存占用应该可以进一步优化，每次传送的字符串tmp可以换成定长的字符串数组。C++的API还不太熟，暂时写成这样。有C++大神可以交流交流
