leetcode208：实现Trie

题目链接

leetcode

题目描述

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

请你实现 Trie 类：

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

C++ 代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

/*
    Trie (前缀树)

    定义前缀树结点的结构
        每个结点包含 26 个子节点的指针，
        bool 变量表示是否为一个单词的结尾。
    插入时沿着根结点向下寻找
        若不存在该路径，则创建结点来生成路径。
    查询或查询前缀时，沿着路径查找。

    时间复杂度：O(s)
        单次操作的时间复杂度和字符串长度一致。
        插入 O(s)，查询 O(s)，查询前缀 O(s)
    空间复杂度：O(nK)
        n 是结点个数，K 是每个结点的分枝数（字符集的大小）。
*/
class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    // 析构函数（工程中需要）
    ~Trie() {
        queue<TrieNode*> q;
        q.push(root);

        while (!q.empty()) {
            TrieNode* node = q.front(); q.pop();
            for (int i = 0; i < TrieNode::N; i++) {
                if (node->child[i] != nullptr) {
                    q.push(node->child[i]);
                }
            }

            delete node;
        }
    }
    
    void insert(string word) {
        TrieNode* p = root;
        for (const char& c : word) {
            int index = c - 'a';
            if (p->child[index] == nullptr) {
                p->child[index] = new TrieNode();
            }
            p = p->child[index];
        }

        p->isEnd = true;
    }
    
    bool search(string word) {
        TrieNode* p = root;
        for (const char& c : word) {
            int index = c - 'a';
            if (p->child[index] == nullptr) {
                return false;
            }
            p = p->child[index];
        }
        
        return p->isEnd;
    }
    
    bool startsWith(string prefix) {
        TrieNode* p = root;
        for (const char& c : prefix) {
            int index = c - 'a';
            if (p->child[index] == nullptr) {
                return false;
            }
            p = p->child[index];
        }
        
        return true;
    }

private:
    struct TrieNode {
        static const int N = 26;
        TrieNode* child[26];
        bool isEnd;

        TrieNode() {
            for (int i = 0; i < N; i++) {
                child[i] = nullptr;
            }
            isEnd = false;
        }
    };

    TrieNode* root;
};

// 辅助函数：打印数组
void printArray(const vector<string>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

// 辅助函数：打印二维数组
void printArray(const vector<vector<string>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Trie trie;
    vector<string> operations = {"Trie", "insert", "search", "search", "startsWith", "insert", "search"};
    vector<vector<string>> params = {{}, {"apple"}, {"apple"}, {"app"}, {"app"}, {"app"}, {"app"}};
    vector<string> output;

    for (int i = 0; i < operations.size(); i++) {
        string op = operations[i];
        if (op == "Trie") {
            output.push_back("null");
        } else if (op == "insert") {
            trie.insert(params[i][0]);
            output.push_back("null");
        } else if (op == "search") {
            bool res = trie.search(params[i][0]);
            output.push_back(res ? "true" : "false");
        } else if (op == "startsWith") {
            bool res = trie.startsWith(params[i][0]);
            output.push_back(res ? "true" : "false");
        }
    }

    cout << "Input: " << endl;
    printArray(operations);
    cout << endl;
    printArray(params);
    cout << endl;
    cout << "Output: " << endl;
    printArray(output);
    cout << endl;

    return 0;
}