题解 | #牛群命名系统# 字典树

class Trie {
  public:
    vector<Trie*> children;
    bool isEnd;
    Trie(): children(26), isEnd(false) {}
    void insert(string name) {
        Trie* node = this;
        for (char ch : name) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }
    bool search(string name) {
        Trie* node = this;
        for (char ch : name) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return false;
            }
            node = node->children[ch];
        }
        return node != nullptr && node->isEnd;
    }
    bool startWith(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return false;
            }
            node = node->children[ch];
        }
        return node != nullptr;
    }
};
class Solution {
  private:
    Trie* T;
    void CowTrie() {
        T = new Trie();
    }
    void insert(string name) {
        T->insert(name);
    }
    bool search(string name) {
        return T->search(name);
    }
    bool startWith(string prefix) {
        return T->startWith(prefix);
    }
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param operations string字符串vector
     * @param args string字符串vector<vector<>>
     * @return string字符串vector
     */
    vector<string> manageCowNames(vector<string>& operations,
                                  vector<vector<string> >& args) {
        vector<string> ans;
        for (int i = 0; i < operations.size(); i++) {
            if (operations[i] == "CowTrie") {
                CowTrie();
                ans.emplace_back("null");
            } else if (operations[i] == "insert") {
                insert(args[i][0]);
                ans.emplace_back("null");
            } else if (operations[i] == "search") {
                if (search(args[i][0])) {
                    ans.emplace_back("true");
                } else {
                    ans.emplace_back("false");
                }
            } else if (operations[i] == "startsWith") {
                if (startWith(args[i][0])) {
                    ans.emplace_back("true");
                } else {
                    ans.emplace_back("false");
                }
            }
        }
        return ans;
    }
};

时间复杂度：字典树相关操作，初始化为O(1)，其余为O(s)，其中 s 为每次插入或查询字符串的长度

空间复杂度：O(t*26)，其中 t 为所有插入字符串长度之和，26即字符集（小写字母）的数量大小