数出以前缀开头的词

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

补全 count_prefix：先走到前缀那个节点，再收集下面所有的词，返回个数。这次数 app 开头的。

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

提交你的答案

请登录后提交答案。

去登录

← app 自己算不算一个词做一个自动补全 →

更多题目

代码编辑器

语言： 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);
}

int count_prefix(TNode* t, const string& pre) {
    TNode* node = walk(t, pre);
    if (node == nullptr) return 0;
    // TODO: 用 collect 把 node 下面所有的词收进一个 vector，返回它的大小
    return -1;
}

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

本次输入：

输出：

👩‍🏫

💬 题目评论

🔒 登录并作答后可看讨论