C++ | Trie + Cache solution | New TLE case explained
Recently went back to re-do this problem and discovered my original solution was no longer working and getting TLE.\n\nThe testcase that was causing the timeout
Recently went back to re-do this problem and discovered my original solution was no longer working and getting TLE.\n\nThe testcase that was causing the timeout was a bunch of identical searches like this:\n`... , ["...z"], ["...z"], ... , ["...z"]`\n\nWithout a cache, we\'re re-doing the same work each on each search - traversing the Trie and checking all the children of each node where there is a wildcard - even though we already know the answer.\nWe can store search results in a cache to return the results of repeated searches in O(1). We just need to be careful though because adding additional words could invalidate the results of our cache. \nIn my implementation, I cleared the cache when adding a word since this was simple. But if anyone has other ideas for a caching strategy please comment :)\n\n```\nstruct TrieNode {\n    bool isWord;\n    unordered_map<char, TrieNode*> next;\n};\n\nclass WordDictionary {\npublic:\n    WordDictionary() {\n        root = new TrieNode();\n    }\n    \n    void addWord(string word) {\n        cache.clear();\n        \n        TrieNode* cur = root;\n        \n        for (char c : word) {\n            if (!cur->next.count(c)) {\n                cur->next[c] = new TrieNode();\n            }\n            cur = cur->next[c];\n        }\n        \n        cur->isWord = true;\n    }\n    \n    bool search(string word) {\n        if (cache.count(word)) {\n            return cache[word];\n        }\n        \n        bool result = searchInNode(word, 0, root);\n        cache[word] = result;\n            \n        return result;\n    }\n    \nprivate:\n    TrieNode* root = nullptr;\n    unordered_map<string, bool> cache;\n    \n    bool searchInNode(string& word, int curPos, TrieNode* node) {\n        if (node == nullptr) {\n            return false;\n        }\n        \n        for (int i = curPos; i < word.length(); i++) {\n            char c = word[i];\n            \n            if (node->next.count(c)) {\n                node = node->next[c];\n            }\n            else {\n                if (c == \'.\') {\n                    for (auto& iter : node->next) {\n                        TrieNode* child = iter.second;\n                        \n                        if (searchInNode(word, i + 1, child)) {\n                            return true;\n                        }\n                    }\n                }\n                \n                return false;\n            }\n        }\n        \n        return node->isWord;\n    }\n};\n```\n
[]