回溯例题集合

Created 02/06/2020 at 01:46PM

记录回溯值得收藏的题目

leetcode T.17

题目

给定一个仅包含数字 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;
}