Minimum Edit Distance C++ | Minimum Edit Distance Dynamic Programming



#include<iostream>
using namespace std;
int main()
{
    int m[200][200], i, j, len1, len2;
    string s1, s2;
    cin>>s1;
    cin>>s2;
    len1=s1.size();
    len2=s2.size();
    for(i=0; i<=len1; i++)
    {
        m[i][0]=i;
    }
    for(j=0; j<=len2; j++)
    {
        m[0][j]=j;
    }
    for(i=1; i<=len1; i++)
    {
        for(j=1; j<=len2; j++)
        {
            if(s1[i-1]==s2[j-1])
                m[i][j]=m[i-1][j-1];
            else
                m[i][j]=min(min(m[i-1][j], m[i][j-1]), m[i-1][j-1])+1;
        }
    }
    cout<<"Changes Needed: "<<m[len1][len2]<<endl;
    return 0;
}


Sample Input:
hello
elo

Sample Output:
Changes Needed: 2

Post a Comment

Previous Post Next Post