给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
class Solution {
private:
void change_res(const char c) {
tmp.clear();
if (c == '2') {
if (res.empty()) {
tmp.emplace_back("a");
tmp.emplace_back("b");
tmp.emplace_back("c");
}
for (const auto& ss : res) {
tmp.emplace_back(ss + "a");
tmp.emplace_back(ss + "b");
tmp.emplace_back(ss + "c");
}
}
else if (c == '3') {
if (res.empty()) {
tmp.emplace_back("d");
tmp.emplace_back("e");
tmp.emplace_back("f");
}
for (const auto& ss : res) {
tmp.emplace_back(ss + "d");
tmp.emplace_back(ss + "e");
tmp.emplace_back(ss + "f");
}
}
else if (c == '4') {
if (res.empty()) {
tmp.emplace_back("g");
tmp.emplace_back("h");
tmp.emplace_back("i");
}
for (const auto& ss : res) {
tmp.emplace_back(ss + "g");
tmp.emplace_back(ss + "h");
tmp.emplace_back(ss + "i");
}
}
else if (c == '5') {
if (res.empty()) {
tmp.emplace_back("j");
tmp.emplace_back("k");
tmp.emplace_back("l");
}
for (const auto& ss : res) {
tmp.emplace_back(ss + "j");
tmp.emplace_back(ss + "k");
tmp.emplace_back(ss + "l");
}
}
else if (c == '6') {
if (res.empty()) {
tmp.emplace_back("m");
tmp.emplace_back("n");
tmp.emplace_back("o");
}
for (const auto& ss : res) {
tmp.emplace_back(ss + "m");
tmp.emplace_back(ss + "n");
tmp.emplace_back(ss + "o");
}
}
else if (c == '7') {
if (res.empty()) {
tmp.emplace_back("p");
tmp.emplace_back("q");
tmp.emplace_back("r");
tmp.emplace_back("s");
}
for (const auto& ss : res) {
tmp.emplace_back(ss + "p");
tmp.emplace_back(ss + "q");
tmp.emplace_back(ss + "r");
tmp.emplace_back(ss + "s");
}
}
else if (c == '8') {
if (res.empty()) {
tmp.emplace_back("t");
tmp.emplace_back("u");
tmp.emplace_back("v");
}
for (const auto& ss : res) {
tmp.emplace_back(ss + "t");
tmp.emplace_back(ss + "u");
tmp.emplace_back(ss + "v");
}
}
else if (c == '9') {
if (res.empty()) {
tmp.emplace_back("w");
tmp.emplace_back("x");
tmp.emplace_back("y");
tmp.emplace_back("z");
}
for (const auto& ss : res) {
tmp.emplace_back(ss + "w");
tmp.emplace_back(ss + "x");
tmp.emplace_back(ss + "y");
tmp.emplace_back(ss + "z");
}
}
else {
return;
}
res.clear();
res = tmp;
}
void traversal(string digits, int index) {
if (index == digits.size()) {
return;
}
const auto integer = digits[index];
change_res(integer);
traversal(digits, index + 1);
}
public:
vector<string> res;
vector<string> tmp;
vector<string> letterCombinations(string digits) {
traversal(digits, 0);
return res;
}
};
class Solution {
private:
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
public:
vector<string> result;
string s;
void backtracking(const string& digits, int index) {
if (index == digits.size()) {
result.push_back(s);
return;
}
int digit = digits[index] - '0'; // 将index指向的数字转为int
string letters = letterMap[digit]; // 取数字对应的字符集
for (int i = 0; i < letters.size(); i++) {
s.push_back(letters[i]); // 处理
backtracking(digits, index + 1); // 递归，注意index+1，一下层要处理下一个数字了
s.pop_back(); // 回溯
}
}
vector<string> letterCombinations(string digits) {
s.clear();
result.clear();
if (digits.size() == 0) {
return result;
}
backtracking(digits, 0);
return result;
}
};