Memory limit Exceeded and the OJ & Run Code judge are singing different songs


  • 0
    K

    I've implemented using simple trie insertion and query mechanism. Similar passed solution on OJ are Accepted but I don't know what's the problem with my implementation.

    One specific testcase is giving Memory limit exceeded on submission. But during "Run code" that test case is not showing any problem. Its not fair to yield two different output on submission and 'Run code'. Then how we are supposed to find the mistake the OJ is trying to indicate? Please fix the 'Run Code' functionality or tell me what's wrong with my implementation.

    My implementation may not be perfect but its certainly not memory limit exceeded. -_-

    class Solution {
        class trieNode {
        public:
            unordered_map<char, trieNode*> children;
            trieNode() {
            }
            ~trieNode() {
                auto node = children.begin();
                while(node != children.end()) {
                    delete node->second;
                    node = children.erase(node);
                }
            }
        };
        
        typedef multimap<trieNode*, int>::iterator mapIterator;
        
        class trie {
        public:
            trieNode* root;
            trie(): root(new trieNode()) {
            }
            ~trie() {
                delete root;
            }
            
            void insert(string& key, int id, multimap<trieNode*, int>& Map) {
                if(key.empty()) return;
                int n = (int)key.length();
                trieNode* pCrawl = root;
                
                for(int i = 0; i < n; ++i) {
                    if(pCrawl->children.find(key[i]) == pCrawl->children.end()) {
                        pCrawl->children[key[i]] = new trieNode();
                    }
                    pCrawl = pCrawl->children[key[i]];
                }
                Map.insert({pCrawl, id});
            }
            
            void queryUtils(int id, trieNode* pCrawl, string& word, multimap<trieNode*, int>& Map, vector<vector<int>>& result) {
                
                for(auto node = pCrawl->children.begin(); node != pCrawl->children.end(); ++node) {
                    pair<mapIterator, mapIterator> range = Map.equal_range(node->second);
                    for(auto it = range.first; it != range.second; ++it) {
                        if(it->second != id) {
                            int id2 = it->second;
                            if(isPalindrome(word, 0, (int)word.length() - 1)) {
                                result.push_back({id2, id});
                            }
                        }
                    }
                    word.push_back(node->first);
                    queryUtils(id, node->second, word, Map, result);
                    word.pop_back();
                }
            }
            
            void query(string& key, int id, multimap<trieNode*, int>& Map, vector<vector<int>>& result) {
                if(key.empty()) return;
                int n = (int)key.length();
                trieNode* pCrawl = root;
                
                for(int i = n - 1; i >= 0; --i) {
                    if(pCrawl->children.find(key[i]) == pCrawl->children.end()) {
                        return;
                    }
                    pCrawl = pCrawl->children[key[i]];
                    pair<mapIterator, mapIterator> range = Map.equal_range(pCrawl);
                    if(isPalindrome(key, 0, i - 1)) {
                        for(auto it = range.first; it != range.second; ++it) {
                            if(it->second != id) {
                                result.push_back(vector<int>{it->second, id});
                            }
                        }
                    }
                }
                string word = "";
                queryUtils(id, pCrawl, word, Map, result);
            }
            
            bool isPalindrome(string& s, int left, int right) {
                while(left < right) {
                    if(s[left++] != s[right--]) {
                        return false;
                    }
                }
                return true;
            }
            
        };
    public:
        vector<vector<int>> palindromePairs(vector<string>& words) {
            vector<vector<int>> result;
            if(words.empty()) return result;
            multimap<trieNode*, int> Map;
            int n = (int)words.size();
            trie* tree = new trie();
            for(int i = 0; i < n; ++i) {
                tree->insert(words[i], i, Map);
            }
            for(int i = 0; i < n; ++i) {
                tree->query(words[i], i, Map, result);
            }
            
            delete tree;
            
            return result;
        }
    };

  • 0
    A

    Have you solve the MLE proplem? I also get a MLE...


  • 0
    A

    BTW, I also try to solve this problem with Trie..


  • 0
    A

    I did it in a similar way using array instead of map and have the exact same problem. I'm assuming it is because of some unseen memory leaks across test cases but I can't find any.


  • 0

    I know this is an old post, but just a note that I have increased the memory limit for C++, so you should not see MLE anymore. Please let me know if your solution still gets MLE.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.