Saturday, January 21, 2012

Edit Distance (DP Solution) Minimum Actions Needed to Transform First String To Second String

#include <iostream>
#include <string>


using namespace std;


int EditDistance(string str1,string str2)
{
    int i,j,cost,dp[100][100];
    str1=" "+str1;
    str2=" "+str2;
    for(i=0;i<str1.size();i++)
        dp[i][0]=i;
    for(j=0;j<str2.size();j++)
        dp[0][j]=j;


    for(i=1;i<str1.size();i++)
        for(j=1;j<str2.size();j++)
        {
            if(str1[i]==str2[j])
                dp[i][j]=dp[i-1][j-1];
            else
            {
                dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
                dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1);
            }
        }
    //deletion dp[i-1][j]+1
    //insertion dp[i][j-1]+1
    //substitution dp[i-1][j-1]+1
    return dp[i-1][j-1];
}
int main()
{
    int a; string str1,str2;
    while(cin >> str1 >> str2)
    {
        a = EditDistance(str1,str2);
        cout << a << endl;
    }
    return 0;
}
/*
kitten
sitting
3
Saturday
Sunday
3
*/

No comments:

Post a Comment