Minimum Edit Distance using Dynamic Programming

The Minimum edit distance between two strings is the minimum number of editing operations required to transform string into other string. Minimum Edit distance use Insertion, Deletion and Substitution operation to transform string into other.

Here I am writing c program to get minimum edit distance between to string using dynamic programming.

Code

public class MinEditDistance
{
public static void main(String[] args)
{
String X="#"+"EXECUTION";
String Y="#"+"INTENTION";
int X_l=X.length();
int Y_l=Y.length();
int D[][]=new int[X_l][Y_l];//Distance Array


//Initialize first row with its index
for (int i = 0; i < X_l; i++)
{
D[i][0]=i;
}
//Initialize first column with its index
for (int j = 0; j < Y_l; j++)
{
D[0][j]=j;
}

for (int i = 1; i < X_l; i++)
{
for (int j = 1; j < Y_l; j++)
{
int min=99999; //reset to infinity
//Get minimum from all
if(X.charAt(i)==Y.charAt(j))
{
min=D[i-1][j-1];
}
if(min > (D[i-1][j-1]+2))
{
min=D[i-1][j-1]+2;
}
if(min > (D[i][j-1]+1))
{
min=D[i][j-1]+1;
}
if(min> (D[i-1][j]+1))
{
min=D[i-1][j]+1;
}

D[i][j]=min;
}
}

//Display Distance Matrix
for (int j = 0; j < Y_l; j++)
{
System.out.print("\t"+Y.charAt(j));
}
System.out.println();
for (int i = 0; i < X_l; i++)
{
System.out.print(X.charAt(i)+"  ");
for (int j = 0; j < Y_l; j++)
{
System.out.print("\t"+D[i][j]);
}
System.out.println();
}

System.out.println("mINIMUM eDIT dISTANCE IS "+D[X_l-1][Y_l-1]);
}

}