int editDistRecursive(String str1 , String str2 , int m ,int n)
{
if (m == 0) return n;
if (n == 0) return m;
if (str1.charAt(m-1) == str2.charAt(n-1))
return editDist(str1, str2, m-1, n-1);
return 1 + min ( editDist(str1, str2, m, n-1),
editDist(str1, str2, m-1, n),
editDist(str1, str2, m-1, n-1)
);
}
int editDistDP(String str1, String str2, int m, int n)
{
int dp[][] = new int[m+1][n+1];
for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++)
{
if (i==0)
dp[i][j] = j;
else if (j==0)
dp[i][j] = i;
else if (str1.charAt(i-1) == str2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 1 + min(dp[i][j-1],
dp[i-1][j],
dp[i-1][j-1]);
}
}
return dp[m][n];
}