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.