211. Design Add and Search Words

class WordDictionary {
private:
    class Node {
      public:
        Node() {}
        // Node(const int& letter_): letter(letter_) {}
        // int letter = -1;
        unordered_map<int, shared_ptr<Node>> next;
    };
    shared_ptr<Node> root;
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        root = make_shared<Node>();
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        addWordToNode(word, 0, this->root);
    }
    
    void addWordToNode(const string& word, const int& index, shared_ptr<Node> node){
        int curr_letter = word[index]-'a';
        // cout << word << " " << word[index] << endl;
        if (node->next.find(curr_letter) == node->next.end()){
            node->next[curr_letter] = make_shared<Node>();
        }
        if (index < word.size() - 1){
            addWordToNode(word, index+1, node->next[curr_letter]);
        }
        else {
            node->next[curr_letter]->next[-1] = make_shared<Node>();
        }
    }
    
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        if (word.size() == 0) {
            return false;
        }
        // return true;
        return searchFromNode(word, 0, this->root);
    }
    
    bool searchFromNode(const string& word, const int& index, shared_ptr<Node> node){
        if (word[index] != '.') {
            int curr_letter = word[index]-'a';
            if (node->next.find(curr_letter) == node->next.end()){
                return false;
            }
            else {
                if (index < word.size() - 1) {
                    return searchFromNode(word, index+1, node->next.at(curr_letter));
                }
                else {
                    return (node->next[curr_letter]->next.find(-1) != node->next[curr_letter]->next.end());
                }
            }
        }
        else {
            if (index == word.size() - 1) {
                for (const auto& [key, value] : node->next) {
                    if (value->next.find(-1) != value->next.end()) {
                        return true;
                    }
                }
                return false;
            }
            else {
                for (const auto& [key, value] : node->next) {
                    if (searchFromNode(word, index+1, value)) {
                        return true;
                    }
                }
                return false;
            }
        }
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

Runtime: 276 ms, faster than 20.66% of C++ online submissions for Design Add and Search Words Data Structure.
Memory Usage: 49.7 MB, less than 7.49% of C++ online submissions for Design Add and Search Words Data Structure.

在看别人答案之前，整理下这里面出现的大小问题。
1，我使用的方法是trie tree，然后这边使用一个新的class叫node，node里面的next表示下一个字母，root表示第0位之前作为引入的node（root的下一个字母即第0个）
2，用shared ptr传递node
3，最主要的问题有两个

• 结尾得有对应的字符，比如-1
• 结尾的.得判断当下所有可能的字符的next有没有-1

别人的答案：不用trie tree，只用unordered map

class WordDictionary {
public:
    /** Initialize your data structure here. */
    unordered_map<int,vector<string>>mp;
    WordDictionary() {
        mp.clear();
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        mp[word.size()].push_back(word);
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool isSame(string str,string word)
    {
        if(str==word) return true;
        int n =word.size();
        for(int i=0;i<n;i++)
        {
            if(word[i]=='.')
                continue;
            else if(word[i]!=str[i])
                return false;
            
        }
        return true;
        
    }
    bool search(string word) {
        int n=word.size();
        if(mp.find(n)!=mp.end())
        {
            auto temp=mp[n];
            for(auto str:temp)
            {
                if(isSame(str,word))
                {
                    return true;
                }
            }
            return false;
        }
        else 
            return false;
    }
};

我自己的复现：

class WordDictionary {
public:
    /** Initialize your data structure here. */
    unordered_map<int, vector<string>> mp;
    WordDictionary() {
        
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        mp[word.size()].push_back(word);
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool isSame(const string& str, const string& word) {
        if (str == word) return true;
        else {
            int length = str.size();
            for (int i=0; i<length; ++i) {
                if (word[i] != str[i] and word[i] != '.') {
                    return false;
                }
            }
        }
        return true;
    }
    
    bool search(string word) {
        for (const auto& str : mp[word.size()]) {
            if (isSame(str, word)) {
                return true;
            }
        }
        return false;
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

Runtime: 84 ms, faster than 98.73% of C++ online submissions for Design Add and Search Words Data Structure.
Memory Usage: 30.8 MB, less than 7.22% of C++ online submissions for Design Add and Search Words Data Structure.