前缀有和没有一起验

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

同一个 suggest。把两个结果的个数拼起来输出：补全 app（有三个）和补全 cat（一个都没有），中间用 / 隔开。

（本题用 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);
    for (auto& kv : node->kids) collect(kv.second, cur + kv.first, out);
}

vector<string> suggest(TNode* t, const string& pre) {
    // 所有以 pre 开头的词，按字典序排好
    vector<string> out;
    TNode* node = walk(t, pre);
    // TODO: 走得通（node 不是 nullptr）才 collect，不然会解引用空指针
    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 << suggest(t, "app").size() << "/" << suggest(t, "cat").size() << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

🔒 登录并作答后可看讨论