_117_'s blog

By _117_, history, 14 months ago, In English

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;
}
  • Vote: I like it
  • -3
  • Vote: I do not like it