第四步前缀搜索

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

补全 collect 里的递归，在 apple、app、apply、banana 里补全 app，把结果按字典序用 / 拼起来输出。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 第三步重复元素的边界交付四种找法一起验收 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <iostream>
#include <string>
#include <vector>
using namespace std;

#include <algorithm>
#include <map>

struct TNode {
    map<char, TNode*> kids;
    bool end = false;      // 有没有一个词在这里结束
};

TNode* build_trie(const vector<string>& words) {
    TNode* root = new TNode();
    for (const string& w : words) {
        TNode* node = root;
        for (char ch : w) {
            if (!node->kids.count(ch)) node->kids[ch] = new TNode();
            node = node->kids[ch];
        }
        node->end = true;
    }
    return root;
}

TNode* walk(TNode* t, const string& pre) {
    // 沿着前缀往下走，走不通返回 nullptr
    TNode* node = t;
    for (char ch : pre) {
        if (!node->kids.count(ch)) return nullptr;
        node = node->kids[ch];
    }
    return node;
}

void collect(TNode* node, const string& cur, vector<string>& out) {
    // 把 node 下面所有的词收进 out
    if (node->end) out.push_back(cur);
    // TODO: 对每个孩子递归收集，路径上加上这个孩子的字符
}

vector<string> suggest(TNode* t, const string& pre) {
    // 所有以 pre 开头的词，按字典序排好
    vector<string> out;
    TNode* node = walk(t, pre);
    if (node != nullptr) collect(node, pre, out);
    sort(out.begin(), out.end());
    return out;
}

string join(const vector<string>& v) {
    string s;
    for (size_t i = 0; i < v.size(); i++) s += (i ? "/" : "") + v[i];
    return s;
}

int main() {
    TNode* t = build_trie({"apple", "app", "apply", "banana"});
    cout << join(suggest(t, "app")) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

🔒 登录并作答后可看讨论