72. Edit Distance

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] minDistance = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i < word1.length() + 1; i++) {
            for (int j = 0; j < word2.length() + 1; j++) {
                if (i == 0) {
                    minDistance[i][j] = j;
                } else if (j == 0) {
                    minDistance[i][j] = i;
                } else if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    minDistance[i][j] = minDistance[i - 1][j - 1];
                } else {
                    minDistance[i][j] = Math.min(Math.min(minDistance[i - 1][j] + 1,  // insert
                                                          minDistance[i][j - 1] + 1),  // delete
                                                 minDistance[i - 1][j - 1] + 1); // replace
                }
            }
        }
        return minDistance[word1.length()][word2.length()];
    }
}

class Solution {
    public int minDistance(String word1, String word2) {
        int[][] visited = new int[word1.length() + 1][word2.length() + 1];
        return minDistance(word1, word2, word1.length(), word2.length(), visited);
    }
    
    private int minDistance(String word1, String word2, int l1, int l2, int[][] visited) {
        if (l1 == 0) {
            return l2;
        }
        if (l2 == 0) {
            return l1;
        }
        if (visited[l1][l2] > 0) {
            return visited[l1][l2];
        }
        int minDistance;
        if (word1.charAt(l1 - 1) == word2.charAt(l2 - 1)) {
            minDistance = minDistance(word1, word2, l1 - 1, l2 - 1, visited);
        } else {
            minDistance = Math.min(Math.min(
                minDistance(word1, word2, l1 - 1, l2, visited) + 1,  // insert
                minDistance(word1, word2, l1, l2 - 1, visited) + 1),  // delete
                minDistance(word1, word2, l1 - 1, l2 - 1, visited) + 1);  // replace
        }
        visited[l1][l2] = minDistance;
        return minDistance;
    }
}