力扣：17. 电话号码的字母组合
描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：
输入：digits = “”
输出：[]
示例 3：
输入：digits = “2”
输出：[“a”,“b”,“c”]
提示：
0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。
1.递归
排列组合的方式，例如：
题目中的“23”，对应为“abc”，“def”,按下2和3时，能出现的选择，只有“a”，“b”，"c"和“d”，“e”，“f”，然而按下第一个数字2，“a”，“b”，"c"不能互相排列，再次按下数字3，“d”，“e”，“f”可以和前面的“a”，“b”，"c"互相组合，组合的可能就为[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
可按照下面设计代码：
1.创建数组，存储第一个数字对应的字母
2.将第二个数字对应的字母，遍历一遍，一一添加到数组中
#include<iostream>
#include<vector>
using namespace std;
class Solution{
public:
string m[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
vector<string> letterCombinations(string digits){
vector<string> res;
for(int i = 0; i < digits.size(); i++){
combine(res,digits[i]);
}
return res;
}
void combine(vector<string> & res,char ch){
int n = res.size();
int digit = static_cast<int>(ch)-48;
int l = m[digit].size();
if(n == 0){
//第一个数字对应的字母添加到数组中
for(auto j = 0; j < l; ++j){
string s(1,m[digit][j]);
res.push_back(s);
}
return;
}
for(int i = 0; i < n; ++i){
//将第二个数字对应的字母，遍历，添加到数组中
for(int j = 0; j < l - 1; ++j){
res.push_back(res[i] + m[digit][j]);
}
res[i] += m[digit][l-1];
}
return;
}
};
int main()
{
Solution solution;
string digits = "79";
vector<string> result = solution.letterCombinations(digits);
cout << "ALL possible combinations for digits " << digits << " are " << endl;
for(const string & str:result){
cout << str << " ";
}
cout << endl;
return 0;
}
2.队列
先将第一个数字对应的字符入队，之后每次从队头取出一个元素，与m[]中字符串中的未组合的字符分别组合，然后放入队尾。
#include<iostream>
#include<queue>
#include<vector>
#include<map>
using namespace std;
class Solution {
public:
vector<string> letterCombinations(string digits) {
map<char, string> m = { {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
{'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"} };
std::queue<string> q;
vector<string> res;
// 先处理第一个数字。是为了使q不为空。
for (auto i : m[digits[0]]) {
string s(1, i);
q.push(s);
}
//处理第二个及以后的数字
for (auto i = 1; i < digits.size(); ++ i) {
int len = q.size();
for (auto j = 0; j < len; ++ j) {
string s = q.front(); //队首的字符
for (auto k = 0; k < m[digits[i]].size(); ++ k) {
q.push(s + m[digits[i]][k]); //队首的字符和余下对应号码未组合的字符组合
}
q.pop(); //删除队首的字符
}
}
while (!q.empty()) {
res.push_back(q.front());
q.pop();
}
return res;
}
};
int main()
{
Solution solution;
string digits = "679";
vector<string> result = solution.letterCombinations(digits);
cout << "All possibile combinations for digits " << digits << " are " << endl;
for(const string & str:result){
cout << str << " ";
}
cout << endl;
return 0;
}
3.搜索(深度优先)
3.1
对一个数字对应的字符都搜索（排列）完成后，在进行第二个数字对应的字符搜索（排列），在进行第三个
和队列的思想类似
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
class Solution{
public:
vector<string> letterCombinations(string digits){
vector<string>res;
if(digits.empty()) return res;
vector<string>letter({"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"});
string path = "";
DFS(digits,0,path,res,letter);
return res;
}
void DFS(string digits, int pos, string & path, vector<string> & res, vector<string> & letter){
if(pos == digits.size()){
res.push_back(path);
return;
}
for(auto c:letter[digits[pos] - '0']){
path.push_back(c);
DFS(digits, pos + 1, path, res, letter);
path.pop_back();
}
}
};
int main()
{
Solution solution;
string digits = "679";
vector<string> result = solution.letterCombinations(digits);
cout << "All possibile combinations for digits " << digits << " are " << endl;
for(const string & str:result){
cout << str << " ";
}
cout << endl;
return 0;
}
3.2
每次递归调用时，将新的字符直接添加到 path 的末尾，而不是像之前那样在函数调用之间不断地对 path 进行 push_back 和 pop_back 操作。这种直接在递归调用中更新 path 的方式避免了频繁的操作，简化了代码逻辑。
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string>res;
if(digits.empty()) return res;
vector<string>letter({"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"});
string path = "";
DFS(digits, 0, path, res, letter);
return res;
}
//此处修改string path,为传值方式
void DFS(string digits, int pos, string path, vector<string>& res, vector<string>& letter){
if(pos == digits.size()){
res.push_back(path);
return;
}
for(auto c: letter[digits[pos] - '0']){
DFS(digits, pos + 1, path + c, res, letter);
}
}
};
int main()
{
Solution solution;
string digits = "679";
vector<string> result = solution.letterCombinations(digits);
cout << "All possibile combinations for digits " << digits << " are " << endl;
for(const string & str:result){
cout << str << " ";
}
cout << endl;
return 0;
}
力扣官方给的解题方法为第三种：
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> combinations;
if (digits.empty()) {
return combinations;
}
unordered_map<char, string> phoneMap{
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
string combination;
backtrack(combinations, phoneMap, digits, 0, combination);
return combinations;
}
void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& combination) {
if (index == digits.length()) {
combinations.push_back(combination);
} else {
char digit = digits[index];
const string& letters = phoneMap.at(digit);
for (const char& letter: letters) {
combination.push_back(letter);
backtrack(combinations, phoneMap, digits, index + 1, combination);
combination.pop_back();
}
}
}
};
![[MRCTF2020]Transform1](https://img-blog.csdnimg.cn/direct/bf55184487954b78b997fb83caa41d1a.png)
![BUUCTF---[MRCTF2020]你传你呢1](https://img-blog.csdnimg.cn/direct/8f6d683d091840879c093b62e9576676.png)
