### _117_'s blog

By _117_, history, 7 weeks ago,

this is the standard Edit Distance problem and this is the code. what is wrong in the code?

int df[5001][5001];

int fun(string& s, string& temp, int ind1, int ind2, int len1, int len2){
int n1 = s.size();
int n2 = temp.size();
if(ind1==n1 or ind2==n2) return abs(len1-len2);

if(df[ind1][ind2]!=-1) return df[ind1][ind2];
int ans=0;

if(s[ind1]==temp[ind2]) ans=fun(s, temp, ind1+1, ind2+1, len1, len2);
else{
// not match
ans=fun(s, temp, ind1+1, ind2+1, len1+1, len2)+1;       // add char to s
ans=min(ans, fun(s, temp, ind1+1, ind2+1, len1, len2+1)+1);    //add char to temp
ans=min(ans, fun(s, temp, ind1+1, ind2+1, len1, len2)+1);    // replace the char
ans=min(ans, fun(s, temp, ind1+1, ind2, len1-1, len2)+1);    // remove char from s
ans=min(ans, fun(s, temp, ind1, ind2+1, len1, len2-1)+1);    // remove char from temp
}

return df[ind1][ind2]=ans;
//return ans;
}

int main(){

txtio;

string s1,s2; cin>>s1>>s2;
memset(df, -1, sizeof(df));
int ans= fun(s1, s2, 0, 0, (int)s1.length(), (int)s2.length());

//print2darr(df, 0, s1.length(), 0, s2.length());

print(ans);

return 0;
}


• -3