Leetcode Hot 100 | 前缀树

思想

前缀树，一种多叉树。用来方便地存储字符串，用途包括自动补全等。

题目

208. Implement Trie (Prefix Tree)

这题让我们实现前缀树，完成插入、查找、查找前缀的方法。

class Trie {
private:
    struct TreeNode {
        bool isEnd;
        TreeNode* children[26];

        TreeNode() {
            isEnd = false;
            memset(children, 0, sizeof(children));
        };
    };
    TreeNode* root;
public:
    Trie() {
        root = new TreeNode();
    }
    
    void insert(string word) {
        TreeNode* curr = root;

        for (char c : word) {
            if (curr->children[c -'a'] == nullptr) {
                curr->children[c - 'a'] = new TreeNode();
            }

            curr = curr->children[c - 'a'];
        }

        curr->isEnd = true;
    }
    
    bool search(string word) {
        TreeNode* curr = root;

        for (char c : word) {
            if (curr->children[c - 'a'] == nullptr) return false;
            curr = curr->children[c - 'a'];
        }

        return curr->isEnd;
    }
    
    bool startsWith(string prefix) {
        TreeNode* curr = root;

        for (char c : prefix) {
            if (curr->children[c - 'a'] == nullptr) return false;
            curr = curr->children[c - 'a'];
        }

        return true;
    }
};

核心在于定义结点结构，结点有一个属性，表示是否有字符串以当前位置结尾，当然还有 26 个指针域，注意使用 memset 进行内存的赋值。

随后的操作都比较平凡，没什么好说的。