Edit Distance of Two Given String [ Amazon ]

Problem:Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1′ into ‘str2′.

a.Insert
b.Remove
c.Replace

All of the above operations are of cost=1.Both the strings are of lowercase.

Hint: Use DP to solve the problem. This problema also can be solved using LCS. LCS needs to be applied on the string and its reverse string.

Link

#include <stdio.h>
#include <string.h>
int _min(int a,int b,int c)
{
    return (a<(b<c?b:c)?a:(b<c?b:c));
}
int main() {
	//code
	int t,n,i,m,j;
	int dp[105][105];
	char str1[105];
	char str2[105];
	scanf("%d",&t);
	while(t--)
	{
	    scanf("%d",&n);
	    scanf("%d",&m);
	    scanf("%s",str1);
	    scanf("%s",str2);
	    
	    for(i=0;i<=strlen(str1);i++)
	    {
	        for(j=0;j<=strlen(str2);j++)
	        {
	            if(i==0)
	            dp[i][j]=j;
	            else if(j==0)
	            dp[i][j]=i;
	            else if(str1[i-1]==str2[j-1])
	            dp[i][j]=dp[i-1][j-1];
	            else if(str1[i-1]!=str2[j-1])
	            dp[i][j]= 1+ 
	            _min(dp[i][j-1],//insert
	            dp[i-1][j-1],//replace
	            dp[i-1][j]);//remove
	        }
	    }
	    printf("%d\n",dp[n][m]);
	}
	return 0;
}