题解 | #编辑距离(二)#

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整型
     */
    //"abc","adc",5,3,100
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        if(str1 == null) {
            if(str2 == null) return 0 ;
            return str2.length() * ic ;
        }
        if(str2 == null) {
            if(str1 == null) return 0 ;
            return str1.length() * ic ;
        }
        char[] arr1 = str1.toCharArray() ;
        char[] arr2 = str2.toCharArray() ;
        //f[i][j]表示将str1的前i个字符编辑成str2的前j个字符 所花费的最小成本
        int f[][] = new int[arr1.length + 1][arr2.length + 1] ;
        for(int i = 0 ; i <= arr1.length ; i ++) {
            for(int j = 0 ; j <= arr2.length ; j ++) {
                if(i == 0) {
                    f[i][j] = ic * j ;
                    continue ;
                } 
                if(j == 0) {
                    f[i][j] = dc * i ;
                    continue ;
                }
                //增加,删除
                f[i][j] =  Math.min(f[i][j-1] + ic , f[i-1][j] + dc) ;
                //替换
                if(arr1[i-1] == arr2[j-1]) {
                    f[i][j] = Math.min(f[i][j] , f[i-1][j-1]) ;
                } else {
                    f[i][j] = Math.min(f[i][j] , f[i-1][j-1] + rc) ;
                }
            }
        }
        return f[arr1.length][arr2.length] ;
    }
}