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

1. 题意

2. 思路

字典树的模版

3. 题解

#include<bits/stdc++.h>
using namespace std;
class Trie {
private:
    vector<Trie*>children;
    int num;
    bool isEnd;
    char ch;
    Trie* searchPrefix(string prefix){
        Trie* node = this;
        for(char ch : prefix) {
            ch = ch - 'a';
            if(node -> children[ch] == nullptr) {
                return nullptr;
            }
            node = node -> children[ch];
        }
        return node;
    }
public:
    Trie() : children(26),num(0),isEnd(false){}
    void insert(string word) {
        Trie* node = this;
        for(char ch : word) {
            char temp = ch;
            ch -= 'a';
            if(node -> children[ch] == nullptr) {
                node -> children[ch] = new Trie;
            }
            node = node -> children[ch];
            node -> ch = temp;
        }
        node -> num = (node -> num) ++;
        node -> isEnd = true;
    }
    bool search(string word) {
        Trie* trie = this -> searchPrefix(word);
        return trie == nullptr ? false : trie -> isEnd;
    }
    bool startsWith(string prefix) {
        Trie* trie = this -> searchPrefix(prefix);
        return trie == nullptr ? false : true;
    }
};
int main()
{
    return 0;
}