Compute the edit distance between the following two strings

Compute the edit distance between the following two strings, using the dynamic programming matrix. S1= THURSDAY S2= TUESDAY What is the optimal alignment of these two strings?

Solution

In TUESDAY insert H between T & U , replace E with R

2 operations

// A Dynamic Programming based Java program to find minimum

// number operations to convert str1 to str2 using matrix

public 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

// isnert 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 last character are different, consider all

// possibilities and find 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 = \"THURSDAY\";

String str2 = \"TUESDAY\";

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

}

}