题解 | #牛群编号变更#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param word1 string字符串 
     * @param word2 string字符串 
     * @return int整型
     */
    public int minDistance (String word1, String word2) {
	  	//先求出最长公共子序列
        int m=word1.length(),n=word2.length();
        int[][] mat=new int[m+1][n+1];
        int max=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                char ch1=word1.charAt(i);
                char ch2=word2.charAt(j);
                if(ch1==ch2){
                    mat[i+1][j+1]=mat[i][j]+1;
                }else{
                    mat[i+1][j+1]=Math.max(mat[i][j+1],mat[i+1][j]);
                }
                if(mat[i+1][j+1]>max) max=mat[i+1][j+1];
            }
        }
        return m+n-max*2;
    }

}