C++ solution WITHOUT Trie, 108 ms
Hi all! I understand that this problem is probably designed especially to see if you know trie data structure. Ok. I\'d like to confess from start that I don\'t
Hi all! I understand that this problem is probably designed especially to see if you know trie data structure. Ok. I\'d like to confess from start that I don\'t know much about this data structure and solve this problem as I\'d do it at work. I just use here map with length of a word as a key and vector of words as a value. And somehow this solution works with 108 ms runtime and 29 mb space.\n\nAfter that I tried to solve this problem using trie and I couldn\'t beat the previous result. I removed the code smart pointers for nodes for better performance accepting memory leaks -> result is still bad. Then I removed containers and used simple array -> the same. Then I took just a solution from the discussion, with memset and NULLs (omg), and it is still worse then my first solution.\n\nThe question is. What kind of solution interviewers wait from the candidate on this problem: unsafe, old-fashioned with memory leaks and slow but with trie or modern, robust and straight-forward WITHOUT trie?\n\nSolution is the following:\n\n```\nclass WordDictionary {\npublic:\n    /** Initialize your data structure here. */\n    WordDictionary() {\n        \n    }\n    \n    /** Adds a word into the data structure. */\n    void addWord(string word) {\n        if (m_words.find(word.length()) == m_words.end()) {\n            m_words[word.length()] = vector<string>();\n        }\n        \n        m_words[word.length()].push_back(word);\n    }\n    \n    /** Returns if the word is in the data structure. A word could contain the dot character \'.\' to represent any one letter. */\n    bool search(string word) {\n        if (m_words.find(word.length()) == m_words.end())\n            return false;\n        \n        for (auto& stored_word : m_words[word.length()]) {\n            \n            bool word_is_matched = true;\n            \n            for (int i = 0; i < word.length(); ++i) {\n                if (word[i] == \'.\')\n                    continue;\n                \n                if (stored_word[i] != word[i]) {\n                    word_is_matched = false;\n                    break;\n                }\n            }\n            \n            if (word_is_matched)\n                return true;\n        }\n        \n        return false;\n    }\n    \nprivate:\n    unordered_map<size_t, vector<string>> m_words;\n};\n```
[]