Trie：小写字符串字典树

算法理解

Trie 的每个节点代表一个前缀；沿着字符对应的边向下走。最后的 isEnd 标记很重要：它区分了“单词存在”与“只是另一个单词的前缀”。

• 复杂度：单词长度为 L 时，插入和查询均为 O(L)。
• 注意：原模板的 10000000 × 26 数组非常耗内存，实际题目应按总字符数开空间。

模板代码

#include <bits/stdc++.h>
using namespace std;
// Trie 字典树
int tree[10000000][26];
bool cnt[10000000];
int idx=0;
void insert(string &str)
{
    int k=0;
    for (int i=0;i<(int)str.size();i++)
    {
        if (!tree[k][str[i]-'a']) tree[k][str[i]-'a']=++idx;
        k=tree[k][str[i]-'a'];
    }
    cnt[k]=true;
}
// 查询是否存在字符串
bool find(string &str)
{
    int k=0;
    for (int i=0;i<(int)str.size();i++)
    {
        if (!tree[k][str[i]-'a']) return false;
        k=tree[k][str[i]-'a'];
    }
    return cnt[k];
}

‍