/* A Dynamic Programming based Java program to find minimum number operations to convert String1 to String2 */

class EditDistance

{

static int min(int x,int y,int z)

{

if (x <= y && x <= z)

return x;

if (y <= x && y <= z)

return y;

else

return z;

}

static int editDistDP(String str1, String str2, int m, int n)

{

// Create a table to store results of subproblems

int dp[][] = new int[m+1][n+1];

// Fill d[][] in bottom up manner

for (int i=0; i<=m; i++)

{

for (int j=0; j<=n; j++)

{

// If first string is empty, only option is to

// insert all characters of second string

if (i==0)

dp[i][j] = j; // Min. operations = j

// If second string is empty, only option is to

// remove all characters of second string

else if (j==0)

dp[i][j] = i; // Min. operations = i

// If last characters are same, ignore last char

// and recur for remaining string

else if (str1.charAt(i-1) == str2.charAt(j-1))

dp[i][j] = dp[i-1][j-1];

// If the last character is different, consider all

// possibilities and find the minimum

else

dp[i][j] = 1 + min(dp[i][j-1], // Insert

dp[i-1][j], // Remove

dp[i-1][j-1]); // Replace

}

}

return dp[m][n];

}

public static void main(String args[])

{

String str1 = "Rohan"; //1st String that need to be converted to 2nd String

String str2 = "Roushan"; //2nd String

System.out.println( editDistDP( str1 , str2 , str1.length(), str2.length()) );

}

}