208-实现前缀树

LeetCode

发布日期: 2021-12-16

LeetCode 208. Implement Trie (Prefix Tree)

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

method

用一个变量isEnd来表示是否单词结束，有26个字母，所以每个节点就有26个子节点，可以用数组存储

class Trie {
public:
    bool isEnd;
    vector<Trie*> next;

    Trie() : isEnd(false), next(26) {}
    
    void insert(string word) {
        Trie* root = this;
        for (auto c : word) {
            int num = c - 'a';
            if (!root->next[num])   // 不存在就创建一个新的节点
                root->next[num] = new Trie();
            root = root->next[num];
        }
        root->isEnd = true; // 设置结束标志
    }
    
    bool search(string word) {
        Trie *node = searchPrefix(word);
        return node && node->isEnd;
    }
    
    bool startsWith(string prefix) {
        Trie *node = searchPrefix(prefix);
        return node;    // 存在就是true
    }

    Trie* searchPrefix(string prefix) {
        Trie *root = this;
        for (auto c : prefix) {
            int num = c - 'a';
            if (!root->next[num]) return nullptr;   // 不存在该前缀
            root = root->next[num]; // 指针一直往后移
        }
        return root;
    }
};

class Trie {
private:
    Trie *next[26];
    bool isEnd;
public:

    Trie() {
        isEnd = false;
        memset(next, 0, sizeof(next));
    }

    void insert(string word) {
        Trie *root = this;
        for (auto ch : word) {
            int num = ch - 'a';
            if (!root->next[num]) {
                root->next[num] = new Trie();
            }
            root = root->next[num];
        }
        root->isEnd = true;
    }
    
    bool search(string word) {
        Trie *root = this;
        for (auto c : word) {
            int num = c - 'a';
            if (!root->next[num]) return false;
            root = root->next[num];
        }
        return root->isEnd;
    }
    
    bool startsWith(string prefix) {
        Trie *root = this;
        for (auto c : prefix) {
            int num = c - 'a';
            if (!root->next[num]) return false;
            root = root->next[num];
        }
        return true;
    }
};

NC124 字典树的实现

字典树又称为前缀树或者Trie树，是处理字符串常用的数据结构。

假设组成所有单词的字符仅是‘a’～‘z’，请实现字典树的结构，并包含以下四个主要的功能。

1. void insert(String word)：添加word，可重复添加；
1. void delete(String word)：删除word，如果word添加过多次，仅删除一次；
1. boolean search(String word)：查询word是否在字典树中出现过(完整的出现过，前缀式不算)；
1. int prefixNumber(String pre)：返回以字符串pre作为前缀的单词数量。

现在给定一个m，表示有m次操作，每次操作都为以上四种操作之一。每次操作会给定一个整数op和一个字符串word，op代表一个操作码，

如果op为1，则代表添加word
op为2则代表删除word
op为3则代表查询word是否在字典树中
op为4代表返回以word为前缀的单词数量（数据保证不会删除不存在的word）。

对于每次操作，

如果op为3时，如果word在字典树中，请输出“YES”，否则输出“NO”
如果op为4时，请输出返回以word为前缀的单词数量，其它情况不输出。

数据范围：操作数满足$0 \le m \le 10^5$，字符串长度都满足$0 \le n \le 200$

进阶：所有操作的时间复杂度都满足 $O(n)$

示例1

输入：[["1","qwer"],["1","qwe"],["3","qwer"],["4","q"],["2","qwer"],["3","qwer"],["4","q"]]
输出：["YES","2","NO","1"]

method

class Trie {
public:
    vector<Trie*> next;
    int num;    // 表示每个前缀的数量
    bool isEnd;
    Trie(): next(26), num(0), isEnd(false) {}
    void insert(string word) {
        Trie *root = this;
        for (auto c : word) {
            int n = c - 'a';
            if (!root->next[n]) {
                root->next[n] = new Trie();
            }
            root = root->next[n];
            root->num++;    // 说明有这个前缀，所以加一
        }
        root->isEnd = true;
    }
    void deleteWord(string word) {
        Trie *root = this;
        for (auto c : word) {
            int n = c - 'a';
            root = root->next[n];
            root->num--;    // 删除了就减一
        }
        if (root->num == 0) root->isEnd = false;
    }
    bool search(string word) {
        Trie *root = this;
        for (auto c : word) {
            int n = c - 'a';
            if (!root->next[n]) return false;
            root = root->next[n];
        }
        return root->isEnd;
    }
    
    int prefixNumber(string pre) {
        Trie *root = this;
        for (auto c : pre) {
            int n = c - 'a';
            if (!root->next[n]) return 0;
            root = root->next[n];
        }
        return root->num;    // 直接返回该前缀数量
    }
};
class Solution {
public:
    vector<string> trieU(vector<vector<string> >& operators) {
        vector<string> res;
        Trie *root = new Trie();
        for (auto op : operators) {
            if (op[0] == "1") {
                root->insert(op[1]);
            } else if (op[0] == "2") {
                root->deleteWord(op[1]);
            } else if (op[0] == "3") {
                if (root->search(op[1])) res.push_back("YES");
                else res.push_back("NO");
            } else {
                res.push_back(to_string(root->prefixNumber(op[1])));
            }
        }
        return res;
    }
};