Why I get memory limit exceeded


  • 0
    R

    I've implemented Levenshtein distance algorithm but in a recursive fashion with a memoization table. I don't understand why this gets the error "Memory Limit Exceeded".

    vector<vector<int>> m;
    int dist(string w, string v,int i, int j)
    {
    	if(i<0 || j<0)
    		return 0;
        if(m[i][j]>=0)
            return m[i][j];
        if (w.length()==0) return v.length();
        if (v.length()==0) return w.length();
        
        int cost = 0;
        if (w.at(i)==v.at(j))
            cost = 0;
        else
            cost = 1;
        
        m[i][j] =  min(min(dist(w,v,i-1,j-1)+cost,dist(w,v,i,j-1)+1),dist(w,v,i-1,j)+1);
        return m[i][j];
    }
    int minDistance(string word1, string word2) {
        if (word1.length()>0)
            m.resize(word1.length());
        else
            return(word2.length());
        if (word2.length()>0)
        {
            for (int i = 0 ; i <m.size();i++)
            {
                m[i].resize(word2.length());
                for (int j = 0 ; j < m[i].size() ; j++)
                    m[i][j] = -1;
            }
        }
        else
            return(word1.length());
        return dist(word1,word2,word1.length()-1,word2.length()-1);
    
    };

Log in to reply
 

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