动态规划实现最小编辑距离算法

1.计算两个字符串最小变更几次变成相同

规则：可以插入、删除、替换单个字母

2. 撸码

/**
 * @description: 最小编辑距离的算法动态规划实现
 * @author: Liangyb (yunbo.liang@ucarinc.com)
 * @create: 2019/12/27 10:30
 */
public class Min_Edit_Distance {

    private static int cost = 0;
    public static int minEdit_distance(String source, String target) {
        //校验合法性
        if(source == null || target == null || "".equals(source) || "".equals(target)){
            return -1;
        }
        if(source.equals(target)){
            return 0;
        }
        //字符串长度
        final int t = target.length();
        final int s = source.length();
        //申请二伟数组存放矩阵
        int[][] distance_matrix = new int[s+1][t+1];
        distance_matrix[0][0] = 0;
        //边界条件初始化
        for(int si=0; si <= s; si++){
            distance_matrix[si][0] = si;
        }
        for(int ti=0; ti <= t; ti++){
            distance_matrix[0][ti] = ti;
        }
        //计算矩阵值
        for(int i=1;i <= s;i++){
            char si = source.charAt(i - 1);
            for(int j=1;j <= t;j++){
                char tj = target.charAt(j - 1);
                if(si == tj){
                    cost = 0;
                }else{
                    cost = 1;
                }
                distance_matrix[i][j] = Math.min(distance_matrix[i-1][j-1]+cost,
                        Math.min(distance_matrix[i-1][j]+1, distance_matrix[i][j-1]+1));
            }
        }
        return distance_matrix[s][t];
    }


    public static void main(String[] args){

        String source = "china";
        String target = "chna";
        System.out.println("最小编辑距离是："+minEdit_distance(source,target));

    }
}