题解 | #密码破译#

使用深度优先搜索，寻找过程中不采用以0开头的数字。

#include <iostream>
#include <vector>
#include <string>
using namespace std;
char digitToChar(int digit){
    return 'a'+(digit-1);
}
void backtrack(string& num, int index, string current, vector<string>& result) {
    // 如果已经处理完所有的数字，并且当前数字串合法，则添加到结果中
    if (index == num.size()) {
        if (current != "") {
            result.push_back(current);
        }
        return;
    }

    for (int i = index; i < num.size()&&i<=index+2; ++i) {
        string substr = num.substr(index, i - index + 1);
        // 检查数字串是否合法
        if (stoi(substr) > 0 && stoi(substr) <= 26 && substr[0]!='0') {
            backtrack(num, i + 1, current + digitToChar(stoi(substr)), result);
        }
    }
}

vector<string> splitNumber(string& num) {
    vector<string> result;
    backtrack(num, 0, "", result);
    return result;
}

int main() {
    string number;
    while (getline(cin,number)) {
        vector<string> result = splitNumber(number);
        for (const auto& str : result) {
            cout << str << " ";
        }
        cout << endl;
    }
    return 0;
}