字典树的实现

C++ 解法, 执行用时: 2ms, 内存消耗: 340KB, 提交时间: 2020-11-29

#include <unordered_map>

class TrieNode {
public:
  TrieNode(bool isEnded=false): end(isEnded), cnt(0) {}
  ~TrieNode() {
    for (auto p : next) { delete p.second; }
  }
  bool end;
  int cnt;
  std::unordered_map<char, TrieNode*> next;
};


class Trie {
public:
  Trie() {
    root = new TrieNode();
  }
  
  void insert(std::string word) {
    TrieNode* curr = root;
    root->cnt++;
    for (auto c : word) {
      auto px = curr->next.find(c);
      if (px==curr->next.end()) {
        curr->next[c] = new TrieNode();
      }
      curr = curr->next[c];
      curr->cnt++;
    }
    curr->end = true;
  }
  
  void remove(std::string word) {
    TrieNode* curr = root;
    root->cnt--;
    for (auto c : word) {
      curr = curr->next[c];
      curr->cnt--;
    }
    curr->end = false;
  }
  
  int count(std::string prefix) {
    TrieNode* curr = root;
    for (auto c : prefix) {
      auto px = curr->next.find(c);
      if (px==curr->next.end()) {
        return 0;
      }
      curr = curr->next[c];
    }
    return curr->cnt;
  }
  
  bool exist(std::string word) {
    TrieNode* curr = root;
    for (auto c : word) {
      auto px = curr->next.find(c);
      if (px==curr->next.end()) {
        return false;
      }
      curr = curr->next[c];
    }
    return curr->end;
  }
  
protected:
  TrieNode* root;
};


class Solution {
public:
    /**
     * 
     * @param operators string字符串vector<vector<>> the ops
     * @return string字符串vector
     */
    vector<string> trieU(vector<vector<string> >& operators) {
        // write code here
        
        std::vector<std::string> outputs;
        Trie trie;

        for (auto op : operators) {
            if (op[0]=="1") {
              trie.insert(op[1]);
            } else if (op[0]=="2") {
              trie.remove(op[1]);
            } else if (op[0]=="3") {
              outputs.push_back(trie.exist(op[1]) ? "YES" : "NO");
            } else {
              outputs.push_back(std::to_string(trie.count(op[1])));
            }
        }
        
        return outputs;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2021-05-04

struct DicTree
{
    int path;
    int end;
    DicTree *map[26];
    DicTree()
    {
        path = 0;
        end = 0;
    }
};

class Solution {
public:
    /**
     * 
     * @param operators string字符串vector<vector<>> the ops
     * @return string字符串vector
     */
    DicTree *root = NULL;
    vector<string> trieU(vector<vector<string> >& operators) 
    {
        vector<string> res;
        for(auto opt:operators)
        {
            if (opt[0] == "1")
            {
                insert(opt[1]);
            }
            else if (opt[0] == "2")
            {
                delnode(opt[1]);
            }
            else if (opt[0] == "3")
            {
                bool bExist = search(opt[1]);
                if (bExist)
                {
                    res.push_back("YES");
                }
                else
                {
                    res.push_back("NO");
                }
                    
            }
            else if (opt[0] == "4")
            {
                int count = prefixNumber(opt[1]);
                res.push_back(to_string(count));
            }
        }
        return res;
    }
    
        
    void insert(string word)
    {
        if (root  == NULL)
        {
            root = new DicTree();
        }
        DicTree *p = root;
        if (word.size() == 0)
        {
            return;
        }
        int index = 0;
        for(int i = 0; i < word.size(); i++)
        {
            index = word[i] - 'a';
            if (p->map[index] == NULL)
            {
                p->map[index] = new DicTree();
            }
            
            p = p->map[index];
            p->path++;
        }
        p->end++;
    }
    
    bool search(string word)
    {    
       
        DicTree *p = root;
        int index = 0;
        for (int i = 0; i < word.size(); i++)
        {
            index = word[i] - 'a';
            if (p->map[index])
            {
                p = p->map[index];
            }
            else
            {
                return false;
            }
        }
        return p->end > 0;
    }
    
    void delnode(string word)
    {
        if (!search(word))
        {
            return ;
        }
        
        DicTree *p = root;
        int index = 0;
        for(int i = 0; i < word.size(); i++)
        {
            index = word[i] - 'a';
            if (p->map[index]->path == 1)
            {
                p->map[index] = NULL;
                return;
            }
            p->map[index]->path--;
            p = p->map[index];
        }
        p->end--;
    }
    
    int prefixNumber(string pre)
    {
        int index = 0;
        DicTree *p = root;
        for(int i = 0; i < pre.size(); i++)
        {
            index = pre[i] - 'a';
            if (p->map[index])
            {
                p = p->map[index];
            }
            else
            {
                return 0;
            }
        }
        return p->path;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2021-04-25

#include<string>
class TrieNode {
public:
    TrieNode(bool end = false, int count = 0) : end_(end), count_(count) { next_.clear(); }
    //~TrieNode() { for (auto p : next_) delete p.second; }
    bool end_;
    int count_;
    unordered_map<char, TrieNode*> next_;
};
class Trie {
public:
    Trie () {root_ = new TrieNode(); }
    void insert(string& word) {
        ++root_->count_;
        TrieNode* cur = root_;
        for (char c : word) {
            if ((cur->next_).count(c) == 0) {
                cur->next_[c] = new TrieNode();
            }
            cur = cur->next_[c];
            ++cur->count_;
        }
        cur->end_ = true;
    }
    void remove(string& word) {
        --root_->count_;
        TrieNode* cur = root_;
        for (char c : word) {
            cur = cur->next_[c];
            --cur->count_;
        }
        cur->end_ = false;
    }
    int count(string& prefix) {
        TrieNode* cur = root_;
        for (char c : prefix) {
            if (cur->next_.count(c) == 0) return 0;
            cur = cur->next_[c];
        }
        return cur->count_;
    }
    bool exist(string& word) {
        TrieNode* cur = root_;
        for (char c : word) {
            if (cur->next_.count(c) == 0) return false;
            cur = cur->next_[c];
        }
        return cur->end_;
    }
    TrieNode* root_;
};
class Solution {
public:
    /**
     * 
     * @param operators string字符串vector<vector<>> the ops
     * @return string字符串vector
     */
    vector<string> trieU(vector<vector<string> >& operators) {
        vector<string> result = {};
        Trie trie;
        for (auto op : operators) {
            if (op[0] == "1") {
                trie.insert(op[1]);
            } else if (op[0] == "2") {
                trie.remove(op[1]);
            } else if (op[0] == "3") {
                result.push_back(trie.exist(op[1]) ? "YES" : "NO");
            } else if (op[0] == "4") {
                result.push_back(to_string(trie.count(op[1])));
            } else {
                continue;
            }
        }
        return result;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2021-02-21

class Trie {
    bool is_string=false;
    Trie* next[26]={nullptr};
    int cnt=0;
public:
    Trie() {    }
    void insert(string word) {
        Trie* root=this;
        for(char w:word){
            if(!root->next[w-'a']) root->next[w-'a']=new Trie();
            root=root->next[w-'a'];
            ++root->cnt;
        }
        root->is_string=true;
    }
    void remove(string word){
        Trie* root=this;
        for(char w:word){
            if(!root->next[w-'a']) return;
            root=root->next[w-'a'];
            --root->cnt;
        }
        if(root->cnt==0) root->is_string=false;
    }
    bool search(string word) {
        Trie* root=this;
        for(char w:word){
            if(!root->next[w-'a']) return false;
            root=root->next[w-'a'];
        }
        return root->is_string;
    }
    int startsWith(string prefix) {
        Trie* root=this;
        for(char w:prefix){
            if(!root->next[w-'a']) return 0;
            root=root->next[w-'a'];
        }
        return root->cnt;
    }
};
class Solution {
public:

    vector<string> trieU(vector<vector<string> >& operators) {
        Trie trie;
        vector<string> res;
        for(auto& op:operators){
            if(op[0]=="1") trie.insert(op[1]);
            else if(op[0]=="2") trie.remove(op[1]);
            else if(op[0]=="3") res.push_back(trie.search(op[1])?"YES":"NO");
            else if(op[0]=="4") res.push_back(to_string(trie.startsWith(op[1])));
        }
        return res;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2020-12-06

class Trie {
    bool is_string=false;
    Trie* next[26]={nullptr};
    int cnt=0;
public:
    /** Initialize your data structure here. */
    Trie() {

    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie* root=this;
        for(char w:word){
            if(!root->next[w-'a']) root->next[w-'a']=new Trie();
            root=root->next[w-'a'];
            ++root->cnt;
        }
        root->is_string=true;
    }
    void remove(string word){
        Trie* root=this;
        for(char w:word){
            if(!root->next[w-'a']) return;
            root=root->next[w-'a'];
            --root->cnt;
        }
        if(root->cnt==0) root->is_string=false;
    }
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie* root=this;
        for(char w:word){
            if(!root->next[w-'a']) return false;
            root=root->next[w-'a'];
        }
        return root->is_string;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    int startsWith(string prefix) {
        Trie* root=this;
        for(char w:prefix){
            if(!root->next[w-'a']) return 0;
            root=root->next[w-'a'];
        }
        return root->cnt;
    }
};

class Solution {
public:
    /**
     * 
     * @param operators string字符串vector<vector<>> the ops
     * @return string字符串vector
     */
    
    vector<string> trieU(vector<vector<string> >& operators) {
        // write code here
        Trie trie;
        vector<string> res;
        for(auto& op:operators){
            if(op[0]=="1") trie.insert(op[1]);
            else if(op[0]=="2") trie.remove(op[1]);
            else if(op[0]=="3") res.push_back(trie.search(op[1])?"YES":"NO");
            else if(op[0]=="4") res.push_back(to_string(trie.startsWith(op[1])));
        }
        return res;
    }
};

详情