q1.Convert this recursion to memoised.
int editDist(string s1, string s2, int idx1, int idx2,int ans)
{
if(idx1<0 && idx2<0)
return 0;
if(idx1<0 && idx2>0)
return idx2+1;
if(idx2<0 && idx1>0)
return idx1+1;
if(s1[idx1]==s2[idx2])
return editDist(s1,s2,idx1-1,idx2-1,ans);
if(s1[idx1]==s2[idx2-1])
return 1+editDist(s1,s2,idx1,idx2-1,ans);
if(s1[idx1-1]==s2[idx2])
return 1+editDist(s1,s2,idx1-1,idx2,ans);
return 1+editDist(s1,s2,idx1-1,idx2-1,ans);
}
//P.S: Ignore the recursive code of qn1. for correctness. I only want to know how to convert that type of qn into memoised.
q2. My ans to qn1. It is wrong but I couldn’t find why. Do tell the wrong logic.
int memo[100][100];
int editDist(string s1, string s2, int idx1, int idx2,int ans)
{
if(memo[idx1][idx2]!=-1) return memo[idx1][idx2];
if(idx1<0 && idx2<0)
ans+=0;
if(idx1<0 && idx2>0)
ans+=idx2+1;
if(idx2<0 && idx1>0)
ans+=idx1+1;
if(s1[idx1]==s2[idx2])
ans+=editDist(s1,s2,idx1-1,idx2-1,ans);
if(s1[idx1]==s2[idx2-1])
ans+=1+editDist(s1,s2,idx1,idx2-1,ans);
if(s1[idx1-1]==s2[idx2])
ans+=1+editDist(s1,s2,idx1-1,idx2,ans);
ans+=1+editDist(s1,s2,idx1-1,idx2-1,ans);
memo[idx1][idx2]=ans;
return ans;
}