[leetcode208]前缀树（模板）

https://leetcode-cn.com/problems/implement-trie-prefix-tree/

说实话 一直以为挺难的东西 认真学了学（好像也没怎么太认真。。。严格意义上来说算是认真学习的第一天吧。。。艹 明天又要开始上英语了） 似乎也没有那么难 看了大佬们的题解之后 差不多可以懂得具体是个什么操作了

TrieNode方式

class TrieNode {
public:
vector<TrieNode*> children;
bool isWord;
TrieNode() : isWord(false), children(26, nullptr) {
}
~TrieNode() {
for (auto& c : children)
delete c;
}
};

class Trie {
public:
/** Initialize your data structure here. */
Trie() {
root = new TrieNode();
}

/\*\* Inserts a word into the trie. \*/
void insert(string word) {
    TrieNode\* p = root;
    for (char a : word) {
        int i = a - 'a';
        if (!p->children\[i\])
            p->children\[i\] = new TrieNode();
        p = p->children\[i\];
    }
    p->isWord = true;
}

/\*\* Returns if the word is in the trie. \*/
bool search(string word) {
    TrieNode\* p = root;
    for (char a : word) {
        int i = a - 'a';
        if (!p->children\[i\])
            return false;
        p = p->children\[i\];
    }
    return p->isWord;
}

/\*\* Returns if there is any word in the trie that starts with the given prefix. \*/
bool startsWith(string prefix) {
    TrieNode\* p = root;
    for (char a : prefix) {
        int i = a - 'a';
        if (!p->children\[i\])
            return false;
        p = p->children\[i\];
    }
    return true;
}

private:
TrieNode* root;
};

作者：fuxuemingzhu
链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/fu-xue-ming-zhu-cong-er-cha-shu-shuo-qi-628gs/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二维数组方式

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50;

class Trie
{
private:
int trie[maxn][26];
int cnt[maxn];
int idx;

public:
Trie()
{
memset(trie, 0, sizeof(trie));
memset(cnt, 0, sizeof(cnt));
idx = 0;
}

void insert(string word)
{
int p = 0;
for (char c : word)
{
int u = c - ‘a’;
if (!trie[p][u])
{
idx++;
trie[p][u] = idx;
}
p = trie[p][u];
}
cnt[p]++; //统计数加1
}

bool search(string word)
{
int p = 0;
for (char c : word)
{
int u = c - ‘a’;
if(!trie[p][u])
{
return false;
}
p = trie[p][u];
}
return cnt[p];
}

bool startsWith(string prefix)
{
int p = 0;
for (char c : prefix)
{
int u = c - ‘a’;
if(!trie[p][u])
{
return false;
}
p = trie[p][u];
}
return true;
}
};

/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/