leetcode 208. 实现 Trie (前缀树)-字典树

谁践踏了优雅 2023-02-27 10:33 83阅读 0赞

**字典树**

[百度百科][Link 1]  
大概是一个26叉树  
**插入**  
**每次插入的时候如果当前没有这个分支就新建节点**

**查找**  
**每次查找都从根节点开始，随着单词的前后顺序如果一直可以查到尾巴  
那么就证明存在**  
**为了和前缀区分  
为每一个单词后面加一个"\}"**  
**因为’\}'的ascii码是’z’的下一个**

#include <iostream>
    #include <map>
    #include <stdio.h>
    
    using namespace std;
    
    #define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    class Trie { 
    public:
        /** Initialize your data structure here. */
    
        struct node{ 
            char c;
            node* children[27] = { nullptr};
            node():c('0'){ }
            node(char c):c(c){ }
        };
    
        node * root;
        Trie() { 
            root = new node('0');
        }
    
        /** Inserts a word into the trie. */
        void insert(string word) { 
            word+= "{";
            node * t = root;
            for(int i = 0;i < word.size();i ++){ 
                if(t->children[word[i] - 'a']== nullptr){ 
                    t->children[word[i] - 'a'] = new node(word[i]);
                }
                t = t->children[word[i] - 'a'];
            }
        }
    
        /** Returns if the word is in the trie. */
        bool search(string word) { 
            word+= "{";
            node * t = root;
            for(int i = 0;i < word.size();i ++){ 
                if(t->children[word[i] - 'a']== nullptr){ 
                    return false;
                }
                if(t->children[word[i] - 'a']->c != word[i]){ 
                    return false;
                }
                t = t->children[word[i] - 'a'];
            }
            return true;
        }
    
        /** Returns if there is any word in the trie that starts with the given prefix. */
        bool startsWith(string prefix) { 
    
            node * t = root;
            for(int i = 0;i < prefix.size();i ++){ 
                if(t->children[prefix[i] - 'a'] == nullptr){ 
                    return false;
                }
    
                if(t->children[prefix[i] - 'a']->c != prefix[i]){ 
                    return false;
                }
                t = t->children[prefix[i] - 'a'];
            }
            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); */
    
    int main()
    { 
        Trie t;
        t.insert("apple");
        debug(t.search("apple"));
        debug(t.search("app"));
        debug(t.startsWith("app"));
    
        t.insert("app");
        debug(t.search("apple"));
        debug(t.search("app"));
        debug(t.startsWith("app"));
        return 0;
    }

![在这里插入图片描述][20200716222540875.png]

[Link 1]: https://baike.baidu.com/item/%E5%AD%97%E5%85%B8%E6%A0%91/9825209?fr=aladdin
[20200716222540875.png]: /images/20230209/e3d6857a33154421aa7d4cf20c7c7074.png