算法训练营Day47

发布时间:2024年01月23日

#Java #动态规划

Feeling and experiences:

编辑距离:力扣题目链接

给你两个单词?word1 和?word2请返回将?word1?转换成?word2 所使用的最少操作数 ?。

你可以对一个单词进行如下三种操作:

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

示例?1:

输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

该题的 dp数组定义 , dp数组初始化 ,递推公式都比较难

主要涉及到了 三个操作:

insert,delete,replace

我对 dp数组的定义是:

?达到 word1 第 i 个字母 与到达 word2第 j 个 字母,最小操作数为dp[i][j]

如果用了该定义,就要对dp数组进行初始化!

class Solution {
    public int minDistance(String word1, String word2) {
    //insert delete replace 操作
    //编辑距离问题

    //创建dp数组 ,定义: 达到 word1 第 i 个字母 与到达 word2第 j 个 字母,最小操作数为dp[i][j]
    int [][]dp = new int[word1.length()+1][word2.length()+1];

    //有增删改 三个操作
    //初始化:
    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++){
            //插入删除可以合并:
            //word1 删除一个  或者  word2 删除一个(可以衍生为 word1加一个)
            if(word1.charAt(i-1) == word2.charAt(j-1)){
                //相等则保持上一个状态
                dp[i][j] = dp[i-1][j-1];
            }else{
                //进行 替换操作 , 只需要替换一个 则 加 1
                //取最小结果
                dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1; //Math.min 只能两两比较
            }
        }
    }
    return dp[word1.length()][word2.length()];
    }
}

这里对 增加 和 删除操作 做了一个巧妙的 合并:

因为 对于word1 增加 一个 字母的操作 ,也就是 word2 删除一个 字母的 操作!

总结思路:

  • 定义状态: 创建一个二维数组 dp,其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小编辑操作数。

  • 初始化:dp[i][0] 初始化为 i,表示将空字符串转换为 word2 的最小编辑操作数为 i;同理,将 dp[0][j] 初始化为 j,表示将 word1 转换为空字符串的最小编辑操作数为 j

  • 递推关系: 使用嵌套的循环遍历 word1word2 的每个字符,通过比较字符是否相等来决定插入、删除或替换操作。如果字符相等,保持上一个状态;如果不相等,选择插入、删除或替换的最小编辑操作数。

两个字符串的删除操作:力扣题目链接

给定两个单词?word1?和?word2?,返回使得?word1?和??word2?相同所需的最小步数

每步?可以删除任意一个字符串中的一个字符。

示例 1:

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ,第二步将 "eat "变为 "ea"

该题 需要对两个字符串进行 删除了

思路基本一致:

class Solution {
    public int minDistance(String word1, String word2) {
    //要对两个 字符串进行删除操作

    //定义dp数组 
     int[][] dp = new int[word1.length() + 1][word2.length() + 1];

     //初始化

        for (int i = 0; i < word1.length() + 1; i++) dp[i][0] = i;
        for (int j = 0; j < word2.length() + 1; j++) dp[0][j] = j;


//循环,递推
         for (int i = 1; i < word1.length() + 1; i++) {
            for (int j = 1; j < word2.length() + 1; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,
                                        Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
    }
    return dp[word1.length()][word2.length()];
    }
}
  • 定义状态: 创建一个二维数组 dp,其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小编辑操作数。

  • 初始化:dp[i][0] 初始化为 i,表示将空字符串转换为 word2 的最小编辑操作数为 i;同理,将 dp[0][j] 初始化为 j,表示将 word1 转换为空字符串的最小编辑操作数为 j

  • 递推关系: 使用嵌套的循环遍历 word1word2 的每个字符,通过比较字符是否相等来决定删除、替换或插入操作。如果字符相等,保持上一个状态;如果不相等,选择删除、替换或插入的最小编辑操作数,分别加上对应的成本。

沙上并禽池上暝,

云破月来花弄影。

Fighting!

文章来源:https://blog.csdn.net/momolinshaomo/article/details/135765486
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。