What is the difference between these two Edit Distance Algorithm

Question

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.

Answer 1

I'm going to assume by "doesn't work" you mean "gives the wrong answer".

In dynamic programming, every cell in the table is supposed to represent a solution to a subproblem. In the case of edit distance, the subproblem is

• Let dp[i][j] be the distance between word1.substring(i) and word2.substring(j)

But in your code, the statement of the subproblem is ambiguous. The cell dp[i][j] contains something that depends on count, but which count? It might very well be that many different counts correspond to the same pair i,j, because you can get to it by different "routes". If that happens, your program will just use whatever count it encountered first, write the answer to the table and never revise it again. Therefore, if the first route you took is not the optimal one, then the result will be wrong.

Consider what happens when I give your program the words "WORD" and "SWORD". Which number will be in dp[3][4]? The correct program will write 0 into that cell, and eventually it will find a route that leads to the point 3,4 and has a cost of 1. Your program, on the other hand, will write the count of the first route it takes, which in this case will be 4. And even though it may later find a better route, it will still trust that 4, because that's what the table says.

In summary, you make a subproblem with the indices i,j depend on some other quantity, which violates the principles of dynamic programming. If your dp table had a third dimension, as in dp[i][j][count], then it might have worked, because then every subproblem would be fully specified.