Edit Distance: the idea to remember.

The core insight

Equal characters advance both indices for free; otherwise take one plus the cheapest insert, delete or replace state.

Why it works

Every optimal edit sequence begins with one of those operations, and suffix distances reuse overlapping decisions.

The mistake to avoid

When one suffix is empty, its distance is the length of the other suffix.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Equal characters advance both indices for free; otherwise take one plus the cheapest insert, delete or replace state.
public int minDistance(String word1, String word2) {
    int m = word1.length() - 1;
    int n = word2.length() - 1;
    int[][] dp = new int[m + 2][n + 2];
    for (int[] d : dp) {
        Arrays.fill(d, -1);
    }
    return helper(word1, word2, m, n, dp);
}

public int helper(String word1, String word2, int m, int n, int[][] dp) {

    if (m + 1 == 0 && n + 1 == 0) {
        return 0;
    }

    if (m + 1 == 0 || n + 1 == 0) {
        return Math.max(m + 1, n + 1);
    }

    if (dp[m][n] != -1) return dp[m][n];
    if (word1.charAt(m) == word2.charAt(n)) {
        dp[m][n] = helper(word1, word2, m - 1, n - 1, dp);
        return dp[m][n];
    } else {

        int delete = 1 + helper(word1, word2, m - 1, n, dp);

        int insert = 1 + helper(word1, word2, m, n - 1, dp);

        int replace = 1 + helper(word1, word2, m - 1, n - 1, dp);

        dp[m][n] = Math.min(Math.min(delete, insert), replace);
        return dp[m][n];
    }
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection