编辑距离(二)

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];
}

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];
    }
}

dp[i][j]表示 str1[0: i] 变为 str2[0: j] 所需要的最少编辑次数
考虑下面几种情况：

• 已知 dp[i - 1][j] ，只需减掉 str1[i]
• 已知 dp[i][j - 1] ，只需加上 str2[j]
• 已知 dp[i - 1][j - 1]
  • str1[i] == str2[j] ，无需操作
  • str1[i] != str2[j] ，修改 str1[i]

import java.util.*;


public class Solution {
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        dp[0][0] = 0;

        for (int i = 1; i <= str1.length(); i++) {
            dp[i][0] = i * dc;
        }
        for (int i = 1; i <= str2.length(); i++) {
            dp[0][i] = i * ic;
        }

        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int ins = dp[i][j - 1] + ic;  // 添加
                    int del = dp[i - 1][j] + dc;  // 删除  
                    int rep = dp[i - 1][j - 1] + rc;  // 替换
                    dp[i][j] = Math.min(ins, Math.min(del, rep));
                }
            }
        }

        return dp[str1.length()][str2.length()];
    }
}

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();
    char[]cs1=str1.toCharArray();
    char[]cs2=str2.toCharArray();
    //
    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(cs1[i-1]==cs2[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[m][n];
    }
}

import java.util.*;

public class Solution {
    public int min(int a,int b){
        return a<b ? a:b;
    }
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        // write code here
        int[][] dp = new int[str1.length()+1][str2.length()+1];
        //str1为空 ，变成str2 是插入操作
        for(int i=0;i<dp[0].length;i++){
            dp[0][i]=i*ic;
        }
        //str1非空 str2为空 是删除操作
        for(int j=0;j<dp.length;j++){
            dp[j][0]=j*dc;
        }
        for(int i=1;i<dp.length;i++){
            for(int j=1;j<dp[0].length;j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){//当前元素匹配 
                    dp[i][j]=dp[i-1][j-1];
                }else{//当前元素不匹配
                    //dp[i-1][j-1]+rc  在str1[0，i-1] 与str2[0,j-1]匹配的情况下需要替换，说明str1[i]需要
                    //dp[i-1][j]+dc   str1[0，i-1] 与str2[0,j]匹配的情况下需要删除，说明str1[i]多余了
                    //dp[i][j-1]+ic   str1[0，i] 与str2[0,j-1]匹配的情况下需要增加，说明str[i]之后还得补一个元素。
                    dp[i][j]=min(dp[i-1][j-1]+rc,min(dp[i-1][j]+dc,dp[i][j-1]+ic ));
                }
            }
        }
        return dp[str1.length()][str2.length()];
    }
}

  /*
    在我看来，此题找状态转移方程是较麻烦的部分，
因此将我理解的三种情况的具体含义记录下来，供网友们参考。       
   1. dp[i][j-1]+ic：  当str1[i]已经和str2[j-1]匹配时，
为使str1[i]和str2[j]匹配，应在str1中插入str2的第j个元素。
   2. dp[i-1][j]+dc：  当str1[i-1]已经和str2[j]匹配时，
为使str1[i]和str2[j]匹配，应删除str1中的第i个元素。
   3. dp[i-1][j-1]+rc：当str1[i-1]已经和str2[j-1]匹配时,
由于str1[i]!=str2[j]，为使str1[i]和str2[j]匹配,应将str1的
第i个元素替换成str2的第j个元素。
  */
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) {
        // write code here
        int n1= str1.length();
        int n2= str2.length();
        if(n1==0) return  n2*ic;
        if(n2==0) return  n1*dc;
        int[][] dp=new int[n1+1][n2+1];
        for (int i=0;i<n1;i++){
            dp[i][0]=i*dc;
        }
        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];
    }
}

import java.util.*;
public class Solution{
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 [][]dp=new int[str1.length()+1][str2.length()+1];
    int l1=str1.length();
    int l2=str2.length();
    
    dp[0][0]=0;
    for(int i=1;i<=l1;i++)dp[i][0]=i*dc;
    for(int j=1;j<=l2;j++)dp[0][j]=j*ic;

    for(int i=1;i<=l1;i++)
    {
        for(int j=1;j<=l2;j++)
        {
            if(str1.charAt(i-1)==str2.charAt(j-1))dp[i][j]=dp[i-1][j-1];
            else
            { 
                //替换
                int choice1=dp[i-1][j-1]+rc;
                //删除
                int choice2=dp[i-1][j]+dc;
                //插入
                int choice3=dp[i][j-1]+ic;
                dp[i][j]=Math.min(Math.min(choice1,choice2),choice3);
            }
        }
        }
     return dp[l1][l2];
}
}

f(x,y):str1 0到x位置字符串str1[0..x] 与 str2中0到y位置字符串str2[0,y] 转换最低代价
如果str1[x] = str2[y] 那么 f(x,y) = f(x-1, y-1)
否则 f(x, y)就等于从

• str1[0...x-1]到str2[0...y-1]转换最低代价 + 一步替换操作代价值，
• str1[0...x-1]到str2[0...y]转换最低代价 + 一步删除操作代价值，
• str1[0...x]到str2[0...y-1]转换最低代价 + 一步插入操作代价值
  三种选择中取值最小的情况，即，

  min(
    f(x-1, y-1) + a
    f(x, y-1) + b
    f(x-1, y) + 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整型
     */
   public  int minEditCost(String str1, String str2, int ic, int dc, int rc) {
        // write code here
        int l1 = str1.length();
        int l2 = str2.length();
        int[][] dp = new int[l1 + 1][l2 + 1];
        for(int i=0; i< l1; ++i){
            dp[i][0] = i * dc;
        }
        for(int i=0; i< l2; ++i){
            dp[0][i] = i * ic;
        }
        for (int i = 1; i <= l1; ++i) {
            for (int j = 1; j <= l2; ++j) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = getMin(
                            // 替换
                            dp[i - 1][j - 1] + rc,
                            // 插入
                            dp[i][j - 1] + ic,
                            // 删除
                            dp[i - 1][j] + dc
                    );
                }
            }
        }
        return dp[l1][l2];
    }
    public  int getMin(int a, int b, int c) {
        return a < b ?
                a < c ? a : c
                :
                b < c ? b : c;
    }

     public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        int n1=str1.length(),n2=str2.length();
        int[][]dp=new int[n1+1][n2+1];//表明分别处理到str1和str2中i和j个元素的最小代价
        for(int i=0;i<n1;i++) dp[i][0]=dc*i;
        for(int i=0;i<n2;i++) dp[0][i]=ic*i;
        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];
    }

 public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        //dp[i][j] 两个串的字符指针位于ij位置时的最小编辑距离 注意预留空的一行一列
        int[][] dp = new int[str1.length()+1][str2.length()+1];
        //初态：第一行第一列需要初始化  
        //dp[i][0] 表示 第一列 以及 str1串有字符i个  str2有0个 如何从Str1变到str2的状态？ 删！
        for (int i = 0; i <= str1.length(); i++) {
            dp[i][0] = i*dc;
        }
        //dp[0][j] 表示 第一行 以及 str1串有字符0个  str2有j个 如何从Str1变到str2的状态？ 增！
        for (int j = 0; j <=str2.length(); j++) {
            dp[0][j] = j*ic;
        }
        //转移方程： 记住所有的dp操作以操作str1为基准
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i-1)==str2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
                else {
                    //三种情况：替换dp[i-1][j-1]+rc,增加dp[i][j-1]+ic,减少dp[i-1][j]+dc
                    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[str1.length()][str2.length()];
    }

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 n = str1.length(), m = str2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= m; i++) dp[0][i] = i * ic;
        for (int i = 0; i <= n; i++) dp[i][0] = i * dc;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int insert = dp[i][j - 1] + ic;
                int delete = dp[i - 1][j] + dc;
                int update = dp[i - 1][j - 1];
                if (str1.charAt(i - 1) != str2.charAt(j - 1)) update += rc;
                dp[i][j] = Math.min(insert, Math.min(delete, update));
            }
        }
        return dp[n][m];
    }
}

/**
     * 牛客网：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];
}