Created 02/06/2020 at 01:46PM
记录回溯值得收藏的题目
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
using namespace std;
void backtrace(string comb, string remain, vector<string> &results, map<int, vector<string>> &info) {
if (remain == "") {
results.push_back(comb);
return;
}
int num = remain[0] - 48;
remain = remain.substr(1);
for (int i = 0; i < info[num].size(); i++) {
backtrace(comb + info[num][i], remain, results, info);
}
return;
}
vector<string> letterCombinations(string digits) {
map<int, vector<string>> info = {
{2, {"a", "b", "c"}},
{3, {"d", "e", "f"}},
{4, {"g", "h", "i"}},
{5, {"j", "k", "l"}},
{6, {"m", "n", "o"}},
{7, {"p", "q", "r", "s"}},
{8, {"t", "u", "v"}},
{9, {"w", "x", "y", "z"}} };
vector<string> out;
backtrace("", digits, out, info);
return out;
}
int main() {
vector<string> TEST = letterCombinations("23");
for (auto ele : TEST) {
cout << ele << endl;
}
system("pause");
return 0;
}