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 | class Solution {
private:
int N;
std::vector<int> digit, cur;
std::vector<std::string> ans;
std::unordered_map<int, std::string> phoneMap = {
{2, "abc"}, {3, "def"}, {4, "ghi"}, {5, "jkl"},
{6, "mno"}, {7, "pqrs"}, {8, "tuv"}, {9, "wxyz"}};
string makeResult() {
string result;
for (int i = 0; i < N; i++)
result += phoneMap[digit[i]][cur[i]];
return result;
}
void dfs(int idx) {
if (idx == N) {
ans.push_back(makeResult());
return;
}
for (int i = 0; i < phoneMap[digit[idx]].size(); i++) {
cur[idx] = i;
dfs(idx + 1);
}
}
public:
vector<string> letterCombinations(string digits) {
for (char c : digits)
digit.push_back(c - '0');
N = digit.size();
cur.assign(N, 0);
ans.clear();
dfs(0);
return ans;
}
};
|