题意概括

你需要实现一个 Trie (前缀树) 数据结构，它需要支持以下三种操作：

• void insert(String word): 向前缀树中插入一个字符串 word。
• boolean search(String word): 查找字符串 word 是否 完整地 存在于前缀树中。
• boolean startsWith(String prefix): 查找前缀树中是否存在以 prefix 开头的单词。

输入格式: 输入为 n 行操作指令，根据指令类型（"Trie", "insert", "search", "startsWith"）和参数，对一个Trie对象进行操作，并对查询操作输出结果。

基础知识

Trie，又称 前缀树 或 字典树，是一种用于高效存储和检索字符串集合的树形数据结构。它的核心思想是利用字符串的公共前缀来减少存储开销和查询时间。

1. 结构:

   • Trie 是一棵多叉树，其中每个节点代表一个字符。
   • 从根节点到任意一个节点的路径构成了一个字符串（前缀）。
   • 每个节点通常包含：
     • 一个指向子节点的指针数组（或哈希表）。对于小写英文字母，通常使用一个大小为 26 的指针数组。
     • 一个布尔标记 isEnd，用于标识从根到该节点的路径是否构成一个完整的、被插入过的单词。

2. 操作逻辑:

   • insert(word): 从根节点开始，沿着 word 中字符对应的路径向下遍历。如果路径中的某个节点不存在，就创建它。遍历结束后，将最后一个字符对应的节点的 isEnd 标记为 true。
   • search(word): 从根节点开始，沿着 word 的路径遍历。如果中途遇到不存在的节点，说明 word 不存在，返回 false。如果成功遍历完所有字符，则需要检查最后一个节点的 isEnd 标记是否为 true。只有为 true，才代表这个单词被完整地插入过。
   • startsWith(prefix): 与 search 类似，从根节点沿着 prefix 的路径遍历。只要能成功遍历完整个 prefix（即路径完整存在），就返回 true，无需关心最后一个节点的 isEnd 标记。

每个操作的时间复杂度均为 $O(L)$，其中 $L$ 是被操作的字符串的长度。

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

// Trie 节点结构体
struct Nde {
    Nde* chd[26];
    bool end;

    Nde() {
        for (int i = 0; i < 26; ++i) {
            chd[i] = nullptr;
        }
        end = false;
    }
};

Nde* rt; // Trie 的根节点

// 初始化
void init() {
    rt = new Nde();
}

// 插入单词
void ins(const string& w) {
    Nde* cur = rt;
    for (char c : w) {
        int idx = c - 'a';
        if (!cur->chd[idx]) {
            cur->chd[idx] = new Nde();
        }
        cur = cur->chd[idx];
    }
    cur->end = true;
}

// 搜索单词
bool src(const string& w) {
    Nde* cur = rt;
    for (char c : w) {
        int idx = c - 'a';
        if (!cur->chd[idx]) {
            return false;
        }
        cur = cur->chd[idx];
    }
    return cur->end;
}

// 搜索前缀
bool stw(const string& p) {
    Nde* cur = rt;
    for (char c : p) {
        int idx = c - 'a';
        if (!cur->chd[idx]) {
            return false;
        }
        cur = cur->chd[idx];
    }
    return true;
}

void run() {
    int n;
    cin >> n;
    
    string op, w;

    for (int i = 0; i < n; ++i) {
        cin >> op;
        if (op == "Trie") {
            init();
        } else if (op == "insert") {
            cin >> w;
            ins(w);
        } else if (op == "search") {
            cin >> w;
            cout << (src(w) ? "true" : "false") << endl;
        } else if (op == "startsWith") {
            cin >> w;
            cout << (stw(w) ? "true" : "false") << endl;
        }
    }
}

int main() {
    // 关闭同步流
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    run();

    return 0;
}

/*
样例 1:
输入:
7
Trie
insert apple
search apple
search app
startsWith app
insert app
search app
输出:
true
false
true
true
*/