LeetCode:实现Trie(前缀树)

208. 实现 Trie (前缀树)

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

思路：

前缀数也叫字典树，是根据依据字符串的前缀构建的树，经典实现用字母代表边，可以用来查询：

• 是否存在某个字符串以某个字符串开始
• 是否真实加入过某个字符串，加入了几次，而不是是否有字符串包含该字符串
  *有多少个字符串以某个字符串为前缀

class Trie {
    struct TrieNode //定义前缀树的结点
    {
        int path; //表示该结点被经过多少次
        int end; //表示有字符串以该结点结尾
        TrieNode *next[26]; //通往26个英文小写字母
        TrieNode()
        {
            path = 0;
            end = 0;
            for (int i = 0; i < 26; i++)
            {
                next[i] = nullptr;
            }
        }
    };
public:
    
    TrieNode *root; //定义根结点
    /** Initialize your data structure here. */
    Trie() {      //构造函数初始化根结点
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode *tmp = root;  //初始化tmp结点
        for (char ch :word) //获取字符串中每一个字符
        {
            int index = ch - 'a'; //获取该字符的index
            if (tmp->next[index] == nullptr) //如果没建立过通往该字符的路径
            {
                tmp->next[index] = new TrieNode(); //则建立
            }
            tmp = tmp->next[index]; //更新tmp
            tmp->path++; //tmp的path++
        }
        tmp->end++; //已该结点结束 end++
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        TrieNode *tmp = root;
        for (char ch : word)
        {
            int index = ch - 'a';
            if (tmp->next[index] == nullptr) //如果没有该路径，返回false
            {
                return false;
            }
            tmp = tmp->next[index];//更新tmp
        }
        if (tmp->end == 0) //如果没以该结点结束，说明该路径只是一个更长字符串的子串，返回false
        {
            return false;
        }
        return true;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        TrieNode *tmp = root;
        for (char ch : prefix)
        {
            int index = ch - 'a';
            if (tmp->next[index] == nullptr)
            {
                return false;
            }
            tmp = tmp->next[index];

        }
        if (tmp->path == 0) //以字符串为前缀，只要求路径中有该字符串即可
        {
            return false;
        }
        return true;
    }
    bool delete(string word)
    {
        if(search(word)) //前缀树中有该字符串才能删除
        {
            TrieNode *tmp = root;
            for(char ch:word)
            {
                int index=ch-'a';
                tmp = tmp->next[index];
                tmp->path--; //路径上的path--
            }
            tmp->end--; //路径结尾end--
            return true;
        }
        else
            return false;
    }
};

/**
 * 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);
 */