Edit Distance is about calculating how similiar 2 Strings are.
The idea is that if 2 Characters do not line up, there is a Cost, or Penalty associated to its current position at that given moment.
In Edit Distance, there is only a few Conditional that takes place to make something similair.
Luckily, we can, in a way, group Insertion/Deletion/Replacement into 1 Conditional, so we only need 2 Conditionals!!!
If both characters are the same, we can call the UP-LEFT diagnol ( which is C[i-1][j-1] ) and set the current value of the Up-Left Diagnols .
So in other words, if this condition is met -- we simply do C[i][j] = C[i-1][j-1]
Again, there is NO COST Penalty because we found a match.. and we Pick Diagnols because going Diagnol is the Fastest way to the end of the Array.
If the program enters this Conditional, what it needs to do is find the Minimum Value of Either, [LEFT, UP, or UP-LEFT] and add +1 to its value.
C[i][j] = Math.min(C[i - 1][j - 1], Math.min(C[i - 1][j], C[i][j - 1])) + 1 ;
public EditString(String string1, String string2) { this.string1 = string1; this.string2 = string2; n = string1.length(); m = string2.length(); // First we need to Create Array[][] to Hold our Data (The **COST** for each step we in order to get to the end) // We add the length of the String +1 to allow create space for our starting place, 0. // We will need to do this for both words. // We name this 'C' because this list is suppose to be our **COST** list C = new int[n+1][m+1]; // Next, we simply initialize the first Row and Column of the Length value of itself. // This will Result in something like (# will be filled with a High value, so I'm Omitting the actual value) // // // J O H N // 0 1 2 3 4 // R 1 0 0 0 0 // A 2 0 0 0 0 // N 3 0 0 0 0 // K 4 0 0 0 0 for (int i = 0; i <= n; i++) C[i][0] = i; for (int j = 0; j <= m; j++) C[0][j] = j; // Now we Iterate, starting @ **1** for (int i=1;i<=string1.length();i++) { for (int j=1;j<=string2.length();j++) { if (string1.charAt(i-1) == string2.charAt(j-1)) { // Since the Char's are the same, there is ***No Cost/Penalty **** // So Store The Upper-Diagnols Value, into the current C[i][j]'s place. C[i][j] = C[i - 1][j - 1]; } else { //IF Char's are not the same, then it will be a Modify/Insert/Delete. // Minimum of Current Values of [LEFT,UP,Up-Left] + 1 -- For the Cost/Penalty of it NOT being a match. C[i][j] = 1 + Math.min(C[i - 1][j - 1], Math.min(C[i - 1][j], C[i][j - 1])); } } } System.out.println("Total Cost: " + C[string1.length()][string2.length()]); }