Lintcode---实现 Trie

向右看齐 2022-03-30 12:58 170阅读 0赞

实现一个 Trie，包含`insert`,`search`, 和`startsWith` 这三个方法。

#####  注意事项 #####

你可以假设所有的输入都是小写字母a-z。

您在真实的面试中是否遇到过这个题？

Yes

**样例**

insert("lintcode")
    search("code") // return false
    startsWith("lint") // return true
    startsWith("linterror") // return false
    insert("linterror")
    search("lintcode) // return true
    startsWith("linterror") // return true

思路：这是一道基本的关于字典树的插入，查询和前缀查询的问题。

本身题目中，插入和查询的过程都非常相似，所以思路相对也很清晰；

**首先正确定义TrieNode节点类，定义时用一个标记位来标记字符串是否存在。然后定义一个节点类型的指针数组，大小为26，用来存放可能存在的节点。**

**插入前先看前缀是否存在。如果存在，就共享，否则创建对应的节点和边。查询过程类似。**

/**
     * Your Trie object will be instantiated and called as such:
     * Trie trie;
     * trie.insert("lintcode");
     * trie.search("lint"); will return false
     * trie.startsWith("lint"); will return true
     */
    
    /*
    思路：这是一道基本的关于字典树的插入，查询和前缀查询的问题。
    
          本身题目中，插入和查询的过程都非常相似，所以思路相对也很清晰；
          
          插入前先看前缀是否存在。如果存在，就共享，否则创建对应的节点和边。
    */
    
    #define MAX_CHILD 26
    
    class TrieNode {
    public:
        // Initialize your data structure here.
        //对于构造函数，需要对对每个节点的指针都进行初始化；
        /*
        任何指针变量刚被创建时不会自动成为NULL指针，它的值是随机的，它会乱指一气。
        所以，指针变量在创建的同时应当被初始化，要么将指针设置为NULL，要么让它指向合法的内存。
        */
        int count;
        TrieNode* child[MAX_CHILD];
        TrieNode() {
            for(int i = 0; i < 26; i++)
                child[i] = NULL;
            count=0;
    
        }
    };
    
    //在这里，我将每个函数的形参都修改成为了pass-by-reference-const,原因是在effective C++ 中
    //建议对于容器使用引用传递可以洁身好多调用拷贝构造函数的时间。
    
    class Trie {
    public:
        Trie() {
            root = new TrieNode();
        }
        
        
    
        // Inserts a word into the trie.
        void insert(const string& word) {
            if(root==NULL||word.size()==0){
                return;
            }
            
            int len=word.size();
            TrieNode* t=root;
            int i=0;
            
            while(i<len){
                //从根节点以下开始查找，看前缀是否存在，如果不存在，则插入节点，如果存在则移动指针；
                if(t->child[word[i]-'a']==NULL){
                    TrieNode* temp=new TrieNode();
                    t->child[word[i]-'a']=temp;
                    t=t->child[word[i]-'a'];
                }
                else{
                    t=t->child[word[i]-'a'];
                }
                i++;
            }
            t->count=1;
        }
    
        // Returns if the word is in the trie.
        //可以看到，查询前缀过程和插入过程十分相似；
        bool search(const string& word) {
            if(root==NULL||word.size()==0){
                return false;
            }
            
            TrieNode* t=root;
            int len=word.size();
            int i=0;
            
            while(i<len){
                if(t->child[word[i]-'a']==NULL){
                    return false;
                }
                else{
                    t=t->child[word[i]-'a'];
                }
                i++;
            }
            
            if((i==len)&&(t->count==1)){
                return true;
            }
            
            return false;
        }
        
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        bool startsWith(const string& prefix) {
            if(root==NULL||prefix.size()==0){
                return false;
            }
            
            int len=prefix.size();
            TrieNode* t=root;
            int i=0;
            
            while(i<len){
                if(t->child[prefix[i]-'a']==NULL){
                    return false;
                }
                else{
                    t=t->child[prefix[i]-'a'];
                }
                i++;
            }
            
            return true;
        }
        
    private:
        TrieNode* root;
    };