# My top-down (c++) solution is timing out...even with memoizing? haaaaalp!!!

• ``````class Solution {
public:
//a memoized top-down DP
int minDistance(string word1, string word2) {
//edge conditions/basecases
if (word1.empty())
return word2.length();
if (word2.empty())
return word1.length();
//dp lookup
pair<string,string> p = make_pair(word1,word2);
map<pair<string,string>,int>::iterator it = memo.find(p);
if (it != memo.end())
return it->second;
//recurrence
int insert_dist  = 1 + (minDistance (word1, word2.substr(1)));
int del_dist     = 1 + (minDistance (word1.substr(1), word2));
int replace_dist = (word1[0] == word2[0] ? 0 : 1) +
(minDistance (word1.substr(1), word2.substr(1)));
int mindist = (min(min(insert_dist, del_dist),replace_dist));

memo[p] = mindist;

return mindist;

}
private:
map<pair<string,string>, int> memo;
};
``````

i'm timing out on some large inputs .. but either way...shouldn't be timing out. any ideas here? i can't use unordered_map with std::pair right out of the box so i went with this. am i not memoizing appropriately? should i have a lookup for each : insert_dist, del_dist, and replace_dist? where it bottoms out before the function call or after seems negligible.

thanks.

• You can try my following concise solution(top down memoized). It gets accepted but still is very slow for C++ solution:

``````class Solution {
public:
int minDistRecur(string s1,string s2,int i,int j,vector<vector<int> >&memo){
if(i==-1)
return j+1;
if(j==-1)
return i+1;
if(memo[i][j]!=-1)
return memo[i][j];
memo[i][j]=min((s1[i]!=s2[j])+minDistRecur(s1,s2,i-1,j-1,memo),min(1+minDistRecur(s1,s2,i-1,j,memo),1+minDistRecur(s1,s2,i,j-1,memo)));
return memo[i][j];
}
int minDistance(string word1, string word2) {
vector<vector<int> >memo(word1.length(), vector<int>(word2.length(),-1));
return minDistRecur(word1,word2,word1.length()-1,word2.length()-1,memo);
}
};``````

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