题解 | #计算字符串的编辑距离#

//两个字符串最短编辑距离
//这道题确实比较难, 注意是状态不知道怎么确定, 
//dp[i][j] 字符串a 的前i个字符 和字符串b 的前j个字符所需的最短编辑距离, 
// 当 a[i-1] == b[j-1]时, dp[i][j] = dp[i-1][j-1]
// 否则  dp[i][j] = min( dp[i-1][j-1]+1 ,dp[i-1][j]+1 ,dp[i][j-1]+1 )
//							替换				插入			删除

import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        String a= sc.nextLine();
        String b = sc.nextLine();
        //定义dp数组, 表示a的前i个字符, 和b的前j的字符 相同所需的编辑距离
        int [][]dp = new int[a.length()+1][b.length()+1];
        //初始化dp数组, 任意一个字符串为空时, 需要的操作次数是另一个字符串的长度
        for (int i = 0; i <= b.length(); i++)
        {
            dp[0][i] = i;
        }
        for (int i = 0; i <= a.length(); i++)
        {
            dp[i][0] = i;
        }

        //给dp数组赋值
        //dp[i][j] = min( dp[i-1][j-1]+1 ,dp[i-1][j]+1 ,dp[i][j-1]+1 )  需要操作
        //                  替换               插入         删除
        //当 a[i]==b[j] 时, dp[i][j] = dp[i-1][j-1]   不需要操作

        //从左到右, 从上到下遍历
        for (int i = 1; i <= a.length(); i++)
        {
            for (int j = 1; j <= b.length(); j++)
            {
                if(a.charAt(i-1)==b.charAt(j-1))
                {
                    dp[i][j] = dp[i-1][j-1];
                }
                else
                {
                    dp[i][j] = Math.min( dp[i-1][j-1]+1 , Math.min( dp[i-1][j]+1 ,dp[i][j-1]+1 ) );
                }
            }
        }
        System.out.println( dp[a.length()][b.length()] );
    }
}