编辑距离(二)_

C/C++

酣饮幻恒

dp[i][j]: 将str1(0-i)编辑成str2(0-j)的最小代价。

dp[i][j] = min(dp[i-1][j] + dc, dp[i][j-1] + ic) : 删掉str1[I]或者插入str2[j]（不管str1[I] 与str2[j]是否相等，都可以这样做）

dp[i][j] = min(dp[i][j], dp[i-1][j-1]) str1[I] = str2[j]

dp[i][j] = min(dp[i][j], dp[i-1][j-1]+ rc) str1[I] != str2[j]

class Solution {
public:
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     */
    int minEditCost(string str1, string str2, int ic, int dc, int rc) {
        // write code here
        int N = str1.length();
        int M = str2.length();
        int dp[N][M];
        dp[0][0] = str1[0] == str2[0] ? 0 : rc;
        for(int i = 1; i < N; i++){
            if(str1[i] == str2[0]){
                dp[i][0] = i * dc;
            }
            else{
                dp[i][0] = min(dp[i-1][0] + dc, rc + i*dc);
            }
        }
        for(int j = 1; j < M; j++){
            if(str1[0] == str2[j]){
                dp[0][j] = j * ic;
            }
            else{
                dp[0][j] = min(dp[0][j-1] + ic, rc + j*ic);
            }
        }
        for(int i = 1; i < N; i++){
            for(int j = 1; j < M; j++){
                dp[i][j] = min(dp[i-1][j] + dc, dp[i][j-1] + ic);
                if(str1[i] == str2[j]){
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1]); 
                }
                else{
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1] + rc);
                }
            }
        }
        return dp[N-1][M-1];
    }
};

发表于 2020-08-31 16:37:26 回复(3)

Edwin_Xu

From https://leetcode-cn.com/problems/edit-distance

发表于 2020-08-28 12:00:23 回复(0)

HollyHANG

一开始把ic和dc加的行列位置写反了，有用例没过

应该注意是从str1→str2，行和列的长度代表的是str1还是str2要分清

import java.util.*;


public class Solution {
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     */
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m + 1][n + 1];    // 行是str1，列是str2，题目要求把str1编辑成str2
        for (int i = 1; i <= m; i++) dp[i][0] = dp[i - 1][0] + dc;    // str1 位置 i 字符 变成 str2 空字符 —— 需要delete
        for (int j = 1; j <= n; j++) dp[0][j] = dp[0][j - 1] + ic;    // str1 空字符 变成 str2 位置 i 字符 —— 需要insert
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    // 字符相同，无需花费cost
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 在insert，delete 和 replace中找到 cost 最小的一个
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + rc, Math.min(dp[i - 1][j] + dc, dp[i][j - 1] + ic));
                }
            }
        }
        return dp[m][n];
    }
}

发表于 2020-08-24 18:12:30 回复(2)

Java

lizi-hust

import java.util.*;
public class Solution {
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        if(str1==null || str2==null) return 0;

        int m = str1.length(), n = str2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i=0; i<=m; i++) dp[i][0] = i*dc;
        for(int i=0; i<=n; i++) dp[0][i] = i*ic;
        
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    int a = dp[i][j-1] + ic;
                    int b = dp[i-1][j] + dc;
                    int c = dp[i-1][j-1] + rc;
                    dp[i][j] = Math.min(a, Math.min(b, c));
                }
            }
        }
        return dp[m][n];
    }
}

发表于 2022-07-22 16:48:00 回复(0)

C/C++

木析

把力扣上面的编辑代价做出来后，我以为我会做了，然后昨天遇到这题还是不会……

看了几个评论区大佬们的题解才勉勉强强写出来了……

还是太菜了……

class Solution {
public:
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     */
    int minEditCost(string str1, string str2, int ic, int dc, int rc) {
        int len1=str1.size(),len2=str2.size();
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
        for(int i=1;i<=len2;i++) {
            dp[0][i]=ic*i; //只能增加
        }
        for(int i=1;i<=len1;i++) {
            dp[i][0]=dc*i; //只能删除
        }
        for(int i=1;i<=len1;i++) {
            for(int j=1;j<=len2;j++) {
                dp[i][j]=min(dp[i-1][j]+dc,dp[i][j-1]+ic);
                int t=dp[i-1][j-1]+((str1[i-1]==str2[j-1])?0:rc);
                dp[i][j]=min(t,dp[i][j]);
//                 cout<<"("<<i<<","<<j<<"):"<<dp[i][j]<<endl;
            }
        }
        return dp[len1][len2];
    }
};

发表于 2021-04-16 15:41:54 回复(0)

duerduer冲啊

摘自力扣评论：

对“dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。”的补充理解：

以 word1 为 "horse"，word2 为 "ros"，且 dp[5][3] 为例，即要将 word1的前 5 个字符转换为 word2的前 3 个字符，也就是将 horse 转换为 ros，因此有：

(1) dp[i-1][j-1]，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 2 个字符 ro，然后将第五个字符 word1[4]（因为下标基数以 0 开始）由 e 替换为 s（即替换为 word2 的第三个字符，word2[2]）

(2) dp[i][j-1]，即先将 word1 的前 5 个字符 horse 转换为 word2 的前 2 个字符 ro，然后在末尾补充一个 s，即插入操作

(3) dp[i-1][j]，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 3 个字符 ros，然后删除 word1 的第 5 个字符

class Solution {
public:
    int minEditCost(string str1, string str2, int ic, int dc, int rc) {
        if(str1==""&&str2=="") return 0;
        int len1 = str1.size();
        int len2 = str2.size();
        //想清楚状态矩阵的定义，下标代表长度！！
        int dp[len1+1][len2+1];
        for(int i=0;i<=len1;i++){
            dp[i][0] = i*dc;//str1所有字符全部删除变成str2
        }
        for(int j=0;j<=len2;j++){
            dp[0][j] = j*ic;//空字符串str1全部插入变成str2
        }
        for(int i=1;i<=len1;i++){
            for(int j=1;j<=len2;j++){
                if(str1[i-1]==str2[j-1]) dp[i][j] = dp[i-1][j-1];
                else{
                    //等价于str1的前i-1个字符和str2的前j-1个字符编辑距离的子问题。
                    //即对于str1的第i个字符'X'，对于str2的第j个字符'W'，我们在str1的末尾'X'替换为字符'W'，
                    //那么dp[i][j]最小可以为dp[i-1][j-1]+rc；
                    int choice1 = dp[i-1][j-1] + rc;//替换
                    
                    //等价于str1的前i个字符和str2的前j-1个字符编辑距离的子问题。
                    //即对于str2的第j个字符'X'，我们在str1的末尾添加了一个相同的字符'X'，
                    //那么dp[i][j]最小可以为dp[i][j-1]+ic；
                    int choice2 = dp[i][j-1]+ic;//插入
                    
                    //等价于str1的前i-1个字符和str2的前j个字符编辑距离的子问题。
                    //即对于str1的第i个字符'X'，我们在str2的末尾添加了一个相同的字符'X'，等价于在str1的末尾删除了该字符'X'，
                    //那么dp[i][j]最小可以为dp[i][j-1]+dc；
                    int choice3 = dp[i-1][j]+dc;//删除
                    dp[i][j] = min(choice1,min(choice2,choice3));
                }
            }
        }
        return dp[len1][len2];
    }
};

编辑于 2021-01-27 23:27:26 回复(3)

Java

永夜201809111855805

/**
     * 牛客网：https://www.nowcoder.com/practice/05fed41805ae4394ab6607d0d745c8e4?tpId=191&tags=&title=&diffculty=0&judgeStatus=0&rp=1
     * 每次操作都有对应的 cost
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     *
     * 解法参考 leetcode 72. 编辑距离
     * 本题比leetcode原题中增加了每种操作的代价。
     *  原题的每种操作代价都是1 
     *  dp[i][j] 表示 word1[0~i] 变成 word2[0~j] 需要的操作次数.
     *  dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
     *  其中：已知 dp[i-1][j] 则 dp[i][j] 删除一个元素变成 dp[i-1][j] ，由 dp[i][j-1] 插入一个字符，由 dp[i-1][j-1] 替换一个元素
     * 
     */
public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
    // 如果其中一个为空
    if (str1.length() == 0) return str2.length() * ic;
    if (str2.length() == 0) return str1.length() * dc;
    int n1 = str1.length(), n2 = str2.length();
    // dp[0][0] 表示空字符串变成空字符串的代价（0），可以简化操作
    int[][] dp = new int[n1 + 1][n2 + 1];
    // 初始化：
    // 1、由 str1 变成空字符串的代价
    for (int i = 0; i <= n1; i++) dp[i][0] = i * dc;
    // 2、由空字符串变成 str2 的代价
    for (int i = 0; i <= n2; i++) dp[0][i] = i * ic;
    // 状态转移
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[i][j] = dp[i-1][j-1];
            else dp[i][j] = Math.min(dp[i-1][j] + dc, Math.min(dp[i][j-1] + ic, dp[i-1][j-1] + rc));
        }
    }
    return dp[n1][n2];
}

发表于 2020-09-06 13:46:56 回复(3)

Fool_one

改自 LeetCode72 编辑距离，+1 操作改成对应的增、删、替换权重即可：

class Solution {
public:
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     */
    int minEditCost(string a, string b, int ic, int dc, int rc) {
        int n = a.size(), m = b.size();
        a = ' ' + a, b = ' ' + b;
        // f[i][j] : 将a[1 - i]变成b[1 - j]的的所有按顺序操作方案的最小值 
        vector<vector<int>> f(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= n; ++i) f[i][0] = i * dc;
        for (int i = 1; i <= m; ++i) f[0][i] = i * ic;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1];
                else {
                    int t1 = f[i - 1][j] + dc;
                    int t2 = f[i][j - 1] + ic;
                    int t3 = f[i - 1][j - 1] + rc;
                    f[i][j] = min(t1, min(t2, t3));
                }
            }
        }
        return f[n][m];
    }
};

[LeetCode72：](https://leetcode-cn.com/problems/edit-distance/)

发表于 2021-05-31 23:11:35 回复(0)

陈jw

class Solution:
    def minEditCost(self , str1 , str2 , ic , dc , rc ):
        str1_length = len(str1)
        str2_length = len(str2)
        dp = [[0 for i in range(str2_length)] for j in range(str1_length)]   # str1的前i个数转换为str2的前j个数的最小cost
        for j in range(str2_length):
            dp[0][j] = dp[0][j - 1] + ic
        for i in range(str1_length):
            dp[i][0] = dp[i - 1][0] + dc
        dp[0][0] = 0 if str1[0] == str2[0] else min(rc, dc + ic)  # 如果第一个数相等，则是为0，反之，则是替换或删除+增加的最小值
        for i in range(1, str1_length):
            for j in range(1, str2_length):
                cost = 0 if str1[i] == str2[j] else min(rc, dc + ic)
                dp[i][j] = min(dp[i-1][j-1] + cost, dp[i-1][j] + dc, dp[i][j-1] + ic)  # 3种情况
        return dp[str1_length-1][str2_length-1]

动态规划的问题：

有三种情况：

1. dp[i-1][j-1] + cost 如果str1[i] = str2[j] 则cost = 0 如果不相等, cost = min(rc, dc+ic)

2. dp[i-1][j]-->dp[i][j] 这个情况下是删除了str1[i]，消耗就是dc

3. dp[i][j-1]-->dp[i][j] 这个情况下是添加了str2[j]，消耗就是ic

发表于 2021-05-12 21:30:33 回复(0)

Java

ningning/

public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        // write code here
        int n1 = str1.length();
        int n2 = str2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];

        for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + dc;
        for (int i = 1; i <= n2; i++) dp[0][i] = dp[0][i - 1] + ic;
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    dp[i][j] = Math.min(dp[i-1][j-1] + rc,Math.min(dp[i-1][j]+dc,dp[i][j-1]+ic));
                }
            }
        }
        return dp[n1][n2];
    }

编辑于 2024-03-20 14:54:20 回复(0)

JavaScript Node

贾小破

function minEditCost( str1 , str2 , ic , dc , rc ) {

// write code here

let len1 = str1.length, len2 = str2.length;

let dp = new Array(len2 + 1).fill(0);

for(let i = 1; i <= len2; i++) {

dp[i] = i * ic;

}

for(let i = 1; i <= len1; i++) {

let pre = dp[0];

dp[0] = i * dc;

for(let j = 1; j <= len2; ++j) {

let tmp = dp[j];

if(str1[i - 1] === str2[j - 1]) dp[j] = pre;

else dp[j] = Math.min(pre + rc, dp[j - 1] + ic, tmp + dc);

pre = tmp;

}

return dp[len2];

}

发表于 2024-03-06 18:34:07 回复(0)

Java

牛客839384289号

public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
    // write code here
    int len1=str1.length() ,len2=str2.length();
    int[][] dp=new int[len1+1][len2+1];
    for(int i=0;i<=len1;i++){
        for(int j=0;j<=len2;j++){
            if(i==0 && j==0){
                dp[i][j]=0;
            }else if(i==0){// 1、从null编辑到j，定义为不断ic
                dp[i][j]=j*ic;
            }else if(j==0){// 2、从i编辑为null,定义为不断dc
                dp[i][j]=i*dc;
            }else if(str1.charAt(i-1)==str2.charAt(j-1)){// 3、两边下一个字符相等，代价为0，则等于上一次代价
                dp[i][j]=dp[i-1][j-1];
            }else{ // 4、如果下一个字符不相等，那么需要看三种代价的最小值
                dp[i][j]=Math.min(Math.min(dp[i-1][j-1]+rc ,dp[i-1][j]+dc) ,dp[i][j-1]+ic);
            }
        }
    }
    return dp[len1][len2];
}

发表于 2024-03-03 13:38:51 回复(0)

Java

fleapx

public int minEditCost(String word1, String word2, int ic, int dc, int rc) {
        // 输出将str1编辑成str2的最小代价
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        // 第一行：是 word1 为空，变成 word2 最少步数，就是插入操作
        for (int j = 1; j <= n2; j++) {
            dp[0][j] = dp[0][j - 1] + ic;
        }
        // 第一列：是 word2 为空，需要的最少步数，就是删除操作
        for (int i = 1; i <= n1; i++) {
            dp[i][0] = dp[i - 1][0] + dc;
        }

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
                    dp[i][j] = Math.min(dp[i][j - 1] + ic, dp[i - 1][j] + dc);
                    int tmp = Math.min(dp[i - 1][j - 1] + rc, dp[i - 1][j - 1] + ic + dc);
                    dp[i][j] = Math.min(dp[i][j], tmp);
                  /*  dp[i][j] = Math.min(Math.min(dp[i][j - 1] + ic, dp[i - 1][j] + dc),
                        Math.min(dp[i - 1][j - 1] + rc, dp[i - 1][j - 1] + ic + dc));*/
                }
            }
        }
        return dp[n1][n2];
    }

发表于 2023-10-18 15:51:01 回复(0)

kkkk704

#

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

#

# min edit cost

# @param str1 string字符串 the string

# @param str2 string字符串 the string

# @param ic int整型 insert cost

# @param dc int整型 delete cost

# @param rc int整型 replace cost

# @return int整型

#

class Solution:

def minEditCost(self , str1: str, str2: str, ic: int, dc: int, rc: int) -> int:

# write code here

s1 = '0'+str1

s2 = '0'+str2

dp_0 = [i*ic for i in range(len(s2))]

dp = [dp_0]

for j in range(1,len(s1)):

dp.append([j*rc])

for i in range(1,len(s1)):

for j in range(1,len(s2)):

if s1[i] == s2[j]:

dp[i].append(dp[i-1][j-1])

else:

dp[i].append(min(dp[i-1][j-1]+rc,dp[i-1][j]+dc,dp[i][j-1]+ic))

print(dp)

return dp[-1][-1]

发表于 2023-05-05 22:23:34 回复(0)

C

猪猪侠新新酱

/**
 * min edit cost
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @param ic int整型 insert cost
 * @param dc int整型 delete cost
 * @param rc int整型 replace cost
 * @return int整型
 */
int minEditCost(char* s, char* t, int ic, int dc, int rc ) {
    // write code here
    int m = strlen(s);
    int n = strlen(t);
    // if (m >= n + 2)
    //     return false;
    int** mined = (int**)malloc(sizeof(int*) * (m + 1));
    for (int i = 0; i <= m; i++) {
        mined[i] = (int*)calloc(n + 1, sizeof(int));
    }
    for (int ii = 1; ii <= m; ii++) {
        mined[ii][0] = ii*dc;
    }
    for (int iii = 1; iii <= n; iii++) {
        mined[0][iii] = iii*ic;
    }
    for (int j = 1; j <= m; j++) {
        for (int k = 1; k <= n; k++) {
            if (s[j - 1] == t[k - 1]) {
                mined[j][k] = mined[j - 1][k - 1];
            } else {
                if ((mined[j - 1][k - 1] + rc) < (mined[j][k - 1] + ic)) {
                    if ((mined[j - 1][k - 1] + rc) < (mined[j - 1][k] + dc)) {
                        mined[j][k] = (mined[j - 1][k - 1] + rc);
                    } else {
                        mined[j][k] = (mined[j - 1][k] + dc);
                    }
                } else {
                    if ((mined[j][k - 1] + ic) < (mined[j - 1][k] + dc)) {
                        mined[j][k] = (mined[j ][k - 1] + ic);
                    } else {
                        mined[j][k] = (mined[j - 1][k] + dc);
                    }

                }
                //mined[j][k]=((mined[j-1][k-1]+1)>(mined[j][k-1]+1):)
            }
        }
    }
    // if (mined[m][n] == 1)
    //     return true;
    return mined[m][n];
}

发表于 2023-01-05 21:42:23 回复(0)

Python3

牛客292060878号

class Solution:
    def minEditCost(self , str1: str, str2: str, ic: int, dc: int, rc: int) -> int:
        # write code here
        m = len(str1)
        n = len(str2)
        dp = [[0 for j in range(n + 1)] for i in range(m + 1)]
        for i in range(1, m + 1):
            dp[i][0] = dp[i - 1][0] + dc
        for j in range(1, n + 1):
            dp[0][j] = dp[0][j - 1] + ic
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j] + dc, dp[i][j - 1] + ic, dp[i - 1][j - 1] + rc)
        return dp[-1][-1]

二维动态规划

发表于 2022-11-08 13:38:51 回复(0)

Go

告白JING

go实现：

func minEditCost(str1 string, str2 string, ic int, dc int, rc int) int {
    n1, n2 := len(str1), len(str2)
    dp := make([][]int, n1+1)
    for i := 0; i <= n1; i++ {
        dp[i] = make([]int, n2+1)
    }
    for i := 1; i <= n1; i++ {
        dp[i][0] += dp[i-1][0] + dc
    }
    for j := 1; j <= n2; j++ {
        dp[0][j] += dp[0][j-1] + ic
    }
    for i := 1; i <= n1; i++ {
        for j := 1; j <= n2; j++ {
            if str1[i-1] == str2[j-1] {
                dp[i][j] = dp[i-1][j-1]
                continue
            }
            dp[i][j] = min(dp[i-1][j]+dc, dp[i][j-1]+ic)
            dp[i][j] = min(dp[i][j], dp[i-1][j-1]+rc)
        }
    }
    return dp[n1][n2]
}
func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

发表于 2022-07-26 14:40:05 回复(0)

Python2

菜鸡升职记

# -*- coding: utf-8 -*-

#
# min edit cost
# @param str1 string字符串 the string
# @param str2 string字符串 the string
# @param ic int整型 insert cost
# @param dc int整型 delete cost
# @param rc int整型 replace cost
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/05fed41805ae4394ab6607d0d745c8e4?tpId=117&&tqId=37801&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
    算法：
        设dp[i][j]表示将字符串str1的前i个字符编辑为字符串str2的前j个字符所需的最小代价
        ic、dc、rc分别代表插入、删除和替换一个字符的代价，m, n分别为str1，str2的长度
        初始化：
            dp[0][0] = 0 # 空字符串 + 空字符串 = 空字符串，无需编辑
        状态转移方程：
            dp[i][0] = i * dc
            dp[0][j] = j * ic
            若str1[i-1] == str2[j-1]：
                dp[i][j] = dp[i - 1][j - 1]
            否则：
                dp[i][j] = min(dp[i][j-1] + ic,  # 对str1插入一个字符，进行匹配，匹配后，str2长度-1
                                dp[i-1][j] + dc # 删除字符str1[i-1]，进行匹配，str1长度-1
                                dp[i - 1][j - 1] + rc) # 替换str1[i - 1]为str2[j - 1]进行匹配，两者长度均-1
        返回值：
            dp[m][n]
    复杂度：
        时间复杂度：O(mn)
        空间复杂度：O(mn)
    """

    def minEditCost(self, str1, str2, ic, dc, rc):
        m, n = len(str1), len(str2)

        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(1, m + 1):  # str2长度为0，只能删除
            dp[i][0] = i * dc

        for j in range(1, n + 1):  # str1长度为0，只能插入
            dp[0][j] = j * ic

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i][j - 1] + ic,
                                   dp[i - 1][j] + dc,
                                   dp[i - 1][j - 1] + rc)

        return dp[m][n]


if __name__ == '__main__':
    s = Solution()

    str1, str2, ic, dc, rc = "abc", "adc", 5, 3, 2

    # str1, str2, ic, dc, rc = "abc", "adc", 5, 3, 100

    res = s.minEditCost(str1, str2, ic, dc, rc)
    print res

发表于 2022-06-24 10:10:55 回复(0)

C++

harrytsz520

class Solution {
public:
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     */
    int minEditCost(string str1, string str2, int ic, int dc, int rc) {
        int n = str1.size(), m = str2.size();
        vector<vector<int>> f(n+1, vector<int>(m+1, INT_MAX));
        for(int i = 0; i <= n; i++) f[i][0] = i*dc;
        for(int i = 0; i <= m; i++) f[0][i] = i*ic;
        
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(str1[i-1] == str2[j-1]) f[i][j] = f[i-1][j-1];
                else f[i][j] = min({f[i-1][j]+dc, f[i][j-1]+ic, f[i-1][j-1]+rc});
            }
        }
        return f[n][m];
    }
};

发表于 2022-05-30 21:31:07 回复(0)

牛客53050838号

较难的动态规划题目(主要要着眼于三个基本操作带来的操作)：
如果选择将str1的前i个字符转换为str2的前j个字符则需要分类讨论->dp[i]j
如果str1[i] == str2[j]->则只需要将前i-1个字符转换为前j-1个字符即可，最后一个字符不动：dp[i][j] = dp[i-1][j-1]
如果str1[i] != str2[j]->分三类操作：
1.插入：将i个字符串转变为前j-1个字符串在插入第j个字符->dp[i][j-1]+ic
2.删除：将i-1个字符串转换为前j个字符串删除第i个字符->dp[i-1][j]+id
3.替换：将i-1个字符串转换为前j-1个字符串替换掉第i个字符为第j个字符->dp[i-1][j-1]+rc
取最小的即可

发表于 2022-05-09 21:14:19 回复(0)

编辑距离(二)

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题