[leetcode208]前缀树(模板)

发布于 2021-10-19  1505 次阅读


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

说实话 一直以为挺难的东西 认真学了学(好像也没怎么太认真。。。严格意义上来说算是认真学习的第一天吧。。。艹 明天又要开始上英语了) 似乎也没有那么难 看了大佬们的题解之后 差不多可以懂得具体是个什么操作了

TrieNode方式

class TrieNode {
public:
    vector<TrieNode*> children;
    bool isWord;
    TrieNode() : isWord(false), children(26, nullptr) {
    }
    ~TrieNode() {
        for (auto& c : children)
            delete c;
    }
};

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode* p = root;
        for (char a : word) {
            int i = a - 'a';
            if (!p->children[i])
                p->children[i] = new TrieNode();
            p = p->children[i];
        }
        p->isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        TrieNode* p = root;
        for (char a : word) {
            int i = a - 'a';
            if (!p->children[i])
                return false;
            p = p->children[i];
        }
        return p->isWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        TrieNode* p = root;
        for (char a : prefix) {
            int i = a - 'a';
            if (!p->children[i])
                return false;
            p = p->children[i];
        }
        return true;
    }
private:
    TrieNode* root;
};

作者:fuxuemingzhu
链接:https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/fu-xue-ming-zhu-cong-er-cha-shu-shuo-qi-628gs/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

二维数组方式

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50;

class Trie
{
private:
  int trie[maxn][26];
  int cnt[maxn];
  int idx;

public:
  Trie()
  {
    memset(trie, 0, sizeof(trie));
    memset(cnt, 0, sizeof(cnt));
    idx = 0;
  }

  void insert(string word)
  {
    int p = 0;
    for (char c : word)
    {
      int u = c - 'a';
      if (!trie[p][u])
      {
        idx++;
        trie[p][u] = idx;
      }
      p = trie[p][u];
    }
    cnt[p]++; //统计数加1
  }

  bool search(string word)
  {
    int p = 0;
    for (char c : word)
    {
      int u = c - 'a';
      if(!trie[p][u])
      {
        return false;
      }
      p = trie[p][u];
    }
    return cnt[p];
  }

  bool startsWith(string prefix)
  {
    int p = 0;
    for (char c : prefix)
    {
      int u = c - 'a';
      if(!trie[p][u])
      {
        return false;
      }
      p = trie[p][u];
    }
    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);
 */

愿风指引你的道路,愿你的刀刃永远锋利。