Why memory limit exceed? Does any one can help?


  • 0
    O
    int strSeqHashVal(const string &str)
    {
        int val=0;
        for(int i=0;i<str.length();i++)
        {
            int tmp=0;
            switch(str[i]){
            case 'A': tmp=0; break;
            case 'C': tmp=1; break;
            case 'G': tmp=2; break;
            case 'T': tmp=3; break;
            }
            val=val*4+tmp;
        }
        return val;
    }
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> result;
        if(s.length()<=10) return result;
        map<int,int>hashCodeFreq;
        map<int,string> codeStrMap;
        
        for(int i=0;i<=s.length()-10;i++){
            int key=strSeqHashVal(s.substr(i,10));
            hashCodeFreq[key]++;
            if(codeStrMap.find(key)==codeStrMap.end()) codeStrMap[key]=s.substr(i,10);
        }
        
        for(map<int,int>::iterator iter=hashCodeFreq.begin();iter!=hashCodeFreq.end();++iter){
            if(iter->second>=2) result.push_back(codeStrMap[iter->first]);
        }
        return result;
    }

  • 2
    Y

    It appears C++ STL set/map of string consumes a lot more memory. One way out is to hash the string into an int, and store map of int's instead. Python set/dict seems ok.


Log in to reply
 

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