用C++代码拉丁字母表有26个字符,而电话只有数字输入板。为了便于输入字母,我们做了一个对应关系。 例如,要输入B,程序要输入22.为了输入相同键上的不同字母,用户在输入之间要停顿一下。 空格' '用来指代停顿。例如2 2代表AA,22代表B
时间: 2024-03-09 13:50:42 浏览: 83
好的,下面是一个C++的实现:
```cpp
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
vector<string> letterCombinations(string digits) {
vector<string> res;
if (digits.empty()) {
return res;
}
unordered_map<char, string> mapping = {
{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
{'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
};
string combination;
backtrack(res, combination, digits, 0, mapping);
return res;
}
void backtrack(vector<string>& res, string& combination, string& digits, int index, unordered_map<char, string>& mapping) {
if (index == digits.size()) {
res.push_back(combination);
return;
}
for (char c : mapping[digits[index]]) {
combination.push_back(c);
backtrack(res, combination, digits, index + 1, mapping);
combination.pop_back();
}
}
int main() {
string digits = "23";
vector<string> res = letterCombinations(digits);
for (string s : res) {
cout << s << " ";
}
cout << endl; // 输出 ad ae af bd be bf cd ce cf
return 0;
}
```
其中,mapping是一个无序映射表,用于存储数字与字母的对应关系。backtrack函数是一个递归函数,用于生成所有可能的字母组合。它的参数combination表示当前已经生成的字母组合,digits表示需要转化为字母的数字串,index表示当前需要转化的数字的下标,mapping表示数字与字母的对应关系。
例如,当digits为"23"时,backtrack函数的执行过程如下:
1. backtrack(res, "", "23", 0, mapping),combination为空,index为0,进入函数体。
2. 枚举mapping["2"]中的所有字母,即'a', 'b', 'c'。
3. combination变为"a",递归调用backtrack(res, "a", "23", 1, mapping)。
4. index为1,继续枚举mapping["3"]中的所有字母,即'd', 'e', 'f'。
5. combination变为"ad",递归调用backtrack(res, "ad", "23", 2, mapping)。
6. index为2,digits.size()为2,说明已经成功地把所有数字都转化为了字母,此时将当前的字母组合"ad"加入结果res中。
7. 回溯到第5步,combination变为"ae",递归调用backtrack(res, "ae", "23", 2, mapping)。
8. index为2,digits.size()为2,将当前的字母组合"ae"加入结果res中。
9. 回溯到第5步,combination变为"af",递归调用backtrack(res, "af", "23", 2, mapping)。
10. index为2,digits.size()为2,将当前的字母组合"af"加入结果res中。
11. 回溯到第2步,combination变为"b",递归调用backtrack(res, "b", "23", 1, mapping)。
12. 枚举mapping["3"]中的所有字母,即'd', 'e', 'f'。
13. combination变为"bd",递归调用backtrack(res, "bd", "23", 2, mapping)。
14. index为2,digits.size()为2,将当前的字母组合"bd"加入结果res中。
15. 回溯到第12步,combination变为"be",递归调用backtrack(res, "be", "23", 2, mapping)。
16. index为2,digits.size()为2,将当前的字母组合"be"加入结果res中。
17. 回溯到第12步,combination变为"bf",递归调用backtrack(res, "bf", "23", 2, mapping)。
18. index为2,digits.size()为2,将当前的字母组合"bf"加入结果res中。
19. 回溯到第2步,combination变为"c",递归调用backtrack(res, "c", "23", 1, mapping)。
20. 枚举mapping["3"]中的所有字母,即'd', 'e', 'f'。
21. combination变为"cd",递归调用backtrack(res, "cd", "23", 2, mapping)。
22. index为2,digits.size()为2,将当前的字母组合"cd"加入结果res中。
23. 回溯到第20步,combination变为"ce",递归调用backtrack(res, "ce", "23", 2, mapping)。
24. index为2,digits.size()为2,将当前的字母组合"ce"加入结果res中。
25. 回溯到第20步,combination变为"cf",递归调用backtrack(res, "cf", "23", 2, mapping)。
26. index为2,digits.size()为2,将当前的字母组合"cf"加入结果res中。
最终的结果res为["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。
阅读全文