LeetCode 72 编辑距离

LeetCode 72 编辑距离

问题描述:
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

执行用时：4 ms, 在所有 Java 提交中击败了99.63%的用户
内存消耗：38.9 MB, 在所有 Java 提交中击败了58.80%的用户

记忆化递归

class Solution {
    public int minDistance(String word1, String word2) {
        //由word1[0:i] -> word2[0:j]
        int[][] memo = new int[word1.length()][word2.length()];
        int ans = dfs(word1, word2, word1.length()-1, word2.length()-1, memo);
        return ans;
    }

    //记忆化递归
    //str1 -> str2
    public int dfs(String str1, String str2, int curr1, int curr2, int[][] memo) {
        //终止条件
        if(curr1<0 || curr2<0) {
            if(curr1<0 && curr2>=0) {
                //插入
                return curr2+1;
            } 
            else if(curr1>=0 && curr2<0) {
                //删除
                return curr1+1;
            }
            else {
                return 0;
            }
        }
        //取记忆
        if(memo[curr1][curr2]!=0) {
            return memo[curr1][curr2];
        }

        //递归过程(回溯)
        int ans = Integer.MAX_VALUE;
        if(str1.charAt(curr1)==str2.charAt(curr2)) {
            ans = dfs(str1, str2, curr1-1, curr2-1, memo);
        }
        else {
            //1. 替换
            ans = Math.min(ans, 
                dfs(str1, str2, curr1-1, curr2-1, memo)+1
            );
            //2. 删除
            ans = Math.min(ans, 
                dfs(str1, str2, curr1-1, curr2, memo)+1
            );
            //3. 插入
            ans = Math.min(ans, 
                dfs(str1, str2, curr1, curr2-1, memo)+1
            );
        }
        //记忆
        if(memo[curr1][curr2]==0) {
            memo[curr1][curr2] = ans;
        }

        //返回值
        return ans;
    }
}