题解 | #奶牛的名字管理#

#include <string>
class NameSystem{
    private:
    vector<bool> nameChar;
    vector<bool> isName;
    NameSystem* next;

    public:
    NameSystem(){
        nameChar.resize(26, false);
        isName.resize(26, false);
        next=nullptr;
    };
    ~NameSystem()=default;  // del先不写
   
    void insert(string name){
         NameSystem* root = this;
         NameSystem* parent = nullptr;
         int i;
         for(i = 0; i<name.size(); ++i){
            if(root == nullptr){
                root = new NameSystem();
            }
            root->nameChar[name[i]-'a'] = true;
            // 指针转换
            if(!parent) parent = root;
            else {
                parent->next = root;
                parent = root;
            }
            root = root->next;
         }
        parent->isName[name[i-1] - 'a'] = true;
    };

    bool search(string name){
        NameSystem* root = this;
        NameSystem* parent = nullptr;
        int i;
        for(i = 0; i<name.size(); ++i){
            if((bool)(root) && root->nameChar[name[i]-'a']){
                parent = root;
                root = root->next;
            }
            else return false;
         }
        
        if(parent->isName[name[i-1]-'a']) return true;
        else return false;

    }

    bool startsWith(string prefix){
        NameSystem* root = this;
        for(int i = 0; i<prefix.size(); ++i){
            if((bool)(root) && (root->nameChar[prefix[i]-'a'])){
                root = root->next;
            }
            else return false;
         }
        return true;
    }
};


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param commands string字符串vector 
     * @param args string字符串vector<vector<>> 
     * @return string字符串vector
     */
    vector<string> cowNameSystem(vector<string>& commands, vector<vector<string>>& args) {
        // write code here
        vector<string> res;
        NameSystem mysystem;
        for (int i = 0; i < commands.size(); ++i)
        {
            if (commands[i] == "insert"){
                mysystem.insert(args[i][0]);
                res.push_back("null");
            }
            else if (commands[i] == "search")
            {
                if(mysystem.search(args[i][0]))
                    res.push_back("true");
                else 
                    res.push_back("false");
            }
            else if  (commands[i] == "startsWith")
            {
                if(mysystem.startsWith(args[i][0])) 
                    res.push_back("true");
                else 
                    res.push_back("false");
            }
        }
        return res;
    }

};