P1245 题解

· · 题解

查找对应字符串，不难想到可以用 substr() 函数进行匹配。

既然是找到合法的一组解，那么可以用深搜查找。

定义字符串 s 和字符串数组 t（分别为密码和单词表），输入字符串 s 和 t_i，定义一个字符串变量 q，q\leftarrow t_i，然后将 t_i 的每一位都改为对应数字，然后用 map 存储 t_i 对应的原字符串 ^1。接下来遍历 t，对每个单词都搜一遍，并将此单词存入 ans 数组中，判断 s.substr(pt, len) == t[k] 的真假 ^2，若为真，pt \leftarrow pt + len，继续往下搜；若为假，返回，将此单词弹出数组，搜另一个。当搜到末尾时 ^3，输出 ans_i 在 map 中对应的元素并结束程序。若搜完所有单词后还没到末尾，输出 No Solutions!。

本题有一个坑点，就是输出字符串的末尾不能有空格，这里在输出字符串区域加一句 if (i != (int)ans.size() - 1) cout << ' '; 即可。

注释：

  1. 我定义了 map<string, string> t2;，修改完后执行 t2[t[i]] = q;。
#include <bits/stdc++.h>

using namespace std;

int n, l;
string s, t[101];
map<string, string> t2;

char modify(char c) {
    char p;
    if (c == 'a' || c == 'b' || c == 'c') p = '1';
    if (c == 'd' || c == 'e' || c == 'f') p = '2';
    if (c == 'g' || c == 'h' || c == 'i') p = '3';
    if (c == 'j' || c == 'k' || c == 'l') p = '4';
    if (c == 'm' || c == 'n') p = '5';
    if (c == 'o' || c == 'p' || c == 'q') p = '6';
    if (c == 'r' || c == 's' || c == 't') p = '7';
    if (c == 'u' || c == 'v' || c == 'w') p = '8';
    if (c == 'x' || c == 'y' || c == 'z') p = '9';
    return p;
}

vector<string> ans;

void dfs(int k, int pt) {
    int len = t[k].size();
    if (s.substr(pt, len) == t[k]) {
        pt += len;
    }
    else {
        return;
    }
    if (pt == l) {
        for (int i = 0; i < (int)ans.size(); ++i) {
            cout << t2[ans[i]];
            if (i != (int)ans.size() - 1) cout << ' ';
        }
        exit(0);
    }
    for (int i = 1; i <= n; ++i) {
        ans.push_back(t[i]);
        dfs(i, pt);
        ans.pop_back();
    }
}

int main() {        

    cin >> n >> s;
    l = s.size();
    for (int i = 1; i <= n; ++i) {
        cin >> t[i];
        string q = t[i];
        int len = t[i].size();
        for (int j = 0; j < len; ++j) {
            t[i][j] = modify(t[i][j]);// 将单词的每一位都改为数字。
        }
        t2[t[i]] = q;// 因为原单词被修改为了数字，这里存储新单词对应的原单词，方便后面输出。
    }
    for (int i = 1; i <= n; ++i) {
        ans.push_back(t[i]);
        dfs(i, 0);
        ans.pop_back();// 复原。
    }
    cout << "No Solutions!";

    return 0;
}