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.