Table of Contents

Trie #

Trie的示意图, 来自OI Wiki(https://oi-wiki.org/string/trie/)

Trie 的作用 #

Trie (字典树/前缀树)是一种树形数据结构, 用于高效地存储和检索字符串数据集中的键. 这一数据结构有相当多的应用情景, 例如自动补完和拼写检查.

Trie 的实现 #

以LeetCode-208 实现 Trie (前缀树)为例.

要求 #

请你实现 Trie 类：

Trie() 初始化前缀树对象
void insert(String word) 向前缀树中插入字符串 word
boolean search(String word) 如果字符串 word 在前缀树中, 返回 true（即在检索之前已经插入）; 否则, 返回 false
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix , 返回 true ; 否则, 返回 false

代码实现 #

class Trie {
private:
    // 递归定义, 每个Trie节点拥有一个长为26的子节点数组, 对应26个后继英文字母
    vector<Trie*> children;
    bool isEnd; // isEnd用来记录以当前节点结尾的前缀是否是一个单词, 用来区分Trie中的前缀与单词

    // searchPrefix方法, 输入一个前缀, 如果Trie中有该前缀, 则返回最后一个节点, 否则返回nullptr
    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch: prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    // 初始化Trie
    Trie() : children(26), isEnd(false) {}
    
    // 插入word, 沿着前缀树寻找, 没有就新建  
    void insert(string word) {
        Trie* node = this;
        for (char ch: word) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }
    
    // 搜索Trie中是否有单词, 调用searchPrefix()方法, 如果存在前缀, 判断是否是一个单词
    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        if (node == nullptr) {
            return false;
        }
        if (node->isEnd == true) {
            return true;
        }
        return false;
    }
    
    // 判断Trie中是否有前缀, 调用searchPrefix()方法即可
    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};