72.编辑距离(递归)

思路和递推版一致, dfs(i,j): word1前i个字符被转化成word2前j个字符需要的最少步数 递归的返回条件分别是记忆化搜索, i/j越界

class Solution {
    int[][] dp;

    /**
     * 思路和递推版一致,
     * dfs(i,j): word1前i个字符被转化成word2前j个字符需要的最少步数
     * 递归的返回条件分别是记忆化搜索, i/j越界
     */
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        dp = new int[n][m];
        for (var arr : dp) {
            Arrays.fill(arr, -1);
        }
        return dfs(word1, word2, word1.length()-1, word2.length()-1);
    }

    private int dfs(String word1, String word2, int i, int j) {
        if (i < 0) {
            return j + 1;
        }
        if (j < 0) {
            return i + 1;
        }
        if (dp[i][j] != -1)
            return dp[i][j];
        if (word1.charAt(i) == word2.charAt(j)) {
            return dp[i][j] = dfs(word1, word2, i-1, j-1);
        } else {
            return dp[i][j] = Math.min(dfs(word1, word2, i-1, j-1), Math.min(
                        dfs(word1, word2, i, j-1), dfs(word1, word2, i-1, j))) + 1;
        }
    }
}