【CT】LeetCode手撕—72. 编辑距离

题目

• 原题连接：72. 编辑距离

1- 思路

模式识别：编辑举例 ——> 动态规划

动规五部曲

1.dp数组的含义

• int[][] dp = new int[word1.length()][word2.length()];
• 以 i-1 为结尾的 word1 和 以 i-2 为结尾的 word2 的 最少操作次数

2.递推公式——比较元素

• 2.1 相等 word1[i] == word2[j] ：此时不考虑第 j-1 个元素和第 i-1 个元素
• 2.2 不相等 word1[i] != word2[j]
  • 增 = 删：
    • 由于不相等，因此删除 word1 的元素，不考虑该元素 此时 =dp[i-1][j]
    • 也可以删除 word2 的元素，此时 =dp[i][j-1]
  • 替换 ：此时 =dp[i-1][j-1] +1
• 递推公式结论：三者里面取最小值

3.初始化

• 由于递推公式，从上到下，从左到右 推导 ——> 初始化第一行 第一列
• dp[i][0] = i ，代表 以 i-1 为结尾的 word1 变为 长为0 的字符串所需要的次数，以 i-1 结尾的字符串长度为 i，因为字符串的下标从 0 开始
• dp[0][j] = j

4.遍历顺序

• 外层 i 从 1 遍历到 i<=wrod1.length
• 内层 j 从 1 遍历到 j<=word2.length

2- 实现

⭐72. 编辑距离——题解思路

class Solution {
    public int minDistance(String word1, String word2) {
        //1. 定义dp数组
        int[][] dp = new int[word1.length()+1][word2.length()+1];

        // 2.递推公式
        // 相等 dp[i][j] = dp[i-1][j-1];
        // 不相等 dp[i][j] = Math.min(dp[i-1]+1,dp[i-1][j-1]+1);

        //3.初始化
        for(int i = 0 ; i <= word1.length();i++){
            dp[i][0] = i;
        }
        for(int j = 0 ; j <= word2.length();j++){
            dp[0][j] = j;
        }

        //4.遍历
        for(int i = 1 ; i <= word1.length() ;i++){
            for(int j = 1 ; j <= word2.length();j++){
                if(word2.charAt(j-1)==word1.charAt(i-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j]+1,Math.min(dp[i][j-1]+1,dp[i-1][j-1]+1));
                }
            }
        }
        return dp[word1.length()][word2.length()];
        }
}

3- ACM 实现

public class editDistance {

    public static int minDistance(String word1,String word2){
        //1.定义dp数组
        int[][] dp = new int[word1.length()+1][word2.length()+1];

        //2.递推公式
        // 相等 dp[i][j] = dp[i-1][j-1]
        // 不相等 dp[i][j] = Math.min(dp[i-1][j]+1,Math.min(dp[i][j-1]+1,dp[i-1][j-1]+1));

        //3.初始化
        for(int i = 0 ; i <= word1.length();i++){
            dp[i][0] = i;
        }
        for(int j = 0 ; j <= word2.length();j++){
            dp[0][j] = j;
        }
        for(int i = 1 ; i <= word1.length();i++){
            for(int j = 1 ; j <= word2.length();j++){
                if(word2.charAt(j-1) == word1.charAt(i-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j]+1,Math.min(dp[i][j-1]+1,dp[i-1][j-1]+1));
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        System.out.println("编辑距离是是"+minDistance(str1,str2));

    }
}