最小编辑代价【Java版】

说明

• leetcode 72 编辑距离 类似

• 注意这里是针对str1变成str2串

• 注意判断两个串为空的情况

• 当两个字符相同的时候，就不用增加代价，直接等于两个串减掉一位的前一个位置的代价

• 当两个串不等的时候，根据插入，删除，替换分别讨论，然后取最小值的代价

  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 m = str1.length();
        int n = str2.length();
  
        int [][] dp = new int[m+1][n+1];
        if(m==0) return  n*ic;
        if(n==0) return m*dc;
        for(int i = 0; i < m; i++) dp[i+1][0] = (i+1)*dc;
        for(int i = 0; i < n; i++) dp[0][i+1] = (i+1)*ic;
  
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(str1.charAt(i)== str2.charAt(j)){
                    dp[i+1][j+1] = dp[i][j];
                }else{
                    /*[i][j+1]   要使i+1和j+1相同 = [i][j+1] + 删除str1的i号元素的代价*/
                    /*[i+1][j]   要使i+1和j+1相同 = [i+1][j] + 向str1中插入和j相同的元素的代价*/
                    /*[i+1][j]   要使i+1和j+1相同 = [i][j] + 把str1中的i+1号元素替换成j+1号元素*/
                    dp[i+1][j+1] = Math.min(dp[i][j+1] + dc, Math.min(dp[i][j]+ rc, dp[i+1][j] + ic));
                }
            }
        }
        return dp[m][n];
    }
  }