Edit Distance is very well known problem in computer science. Came up with following algorithm after reading through CLRS but it doesn't work. Check the working algorithm below, I couldn't find why first algorithm doesn't work while second one does.
public int find (String word1, String word2, int i, int j, int count) {
if (i >= word1.length()) return count + word2.length() - j;
if (j >= word2.length()) return count + word1.length() - i;
if (dp[i][j] != -1) return dp[i][j];
if (word1.charAt(i) == word2.charAt(j)) {
dp[i][j] = find(word1, word2, i+1, j+1, count);
} else {
int replace = find(word1, word2, i+1, j+1, count + 1);
int delete = find(word1, word2, i+1, j, count + 1);
int insert = find(word1, word2, i, j+1, count + 1);
dp[i][j] = Math.min(replace, Math.min(delete, insert));
}
return dp[i][j];
}
Notice, how I'm passing the cost of edit in method argument. Now, the algorithm which works. Here I'm not passing the edit distance in the method parameter instead of I'm adding 1 to recursive method.
public int find (String word1, String word2, int i, int j) {
if (i >= word1.length()) return word2.length() - j;
if (j >= word2.length()) return word1.length() - i;
if (dp[i][j] != -1) return dp[i][j];
if (word1.charAt(i) == word2.charAt(j)) {
dp[i][j] = find(word1, word2, i+1, j+1, count);
} else {
int replace = find(word1, word2, i+1, j+1, count + 1);
int delete = find(word1, word2, i+1, j, count + 1);
int insert = find(word1, word2, i, j+1, count + 1);
dp[i][j] = 1 + Math.min(replace, Math.min(delete, insert));
}
return dp[i][j];
}
I'm not able to think why first algorithm fails. Appreciate, if you can point my error in understanding.