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

import java.util.*;

public class Main {
    static int[][] dp;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s1 = in.next();
        String s2 = in.next();
        int length1 = s1.length();
        int length2 = s2.length();
        dp = new int[length1 + 1][length2 + 1];
        for (int i = 0; i <= length1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= length2; j++) {
            dp[0][j] = j;
        }


        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                int a = dp[i - 1][j] + 1;
                int b = dp[i][j - 1] + 1;
                int c = s1.charAt(i - 1) == s2.charAt(j - 1) ? dp[i - 1][j - 1] : dp[i - 1][j -
                        1] + 1;
                dp[i][j] = Math.min(Math.min(a, b), c);
            }
        }
        System.out.println(dp[length1][length2]);
        in.close();
    }
}

解题思路:

1, 使用了动态规划的思想;

2, 将原字符串前第m个字符组成的字符串, 到目标字符串前第n个字符组成的字符串的最短编辑路径 在数组dp[][]中计为dp[m][n];

3, 原字符串前第m个字符组成的字符串, 到目标字符串前第n个字符组成的字符串的实现, 有三种方式, 这三种方式中最短的编辑路径就是dp[m][n]对应的值:

1: 原字符串前第m-1个字符串变换到目标字符串前第n个字符组成的字符串, 再将原字符串前第m个字符串去掉, 即dp[m][n]=dp[m-1][n]+1;

2: 原字符串前第m个字符串变换到目标字符串前第n-1个字符组成的字符串, 再在目标字符串中补充前第n个字符串去掉, 即dp[m][n]=dp[m][n-1]+1;

3: 如果原字符串第m个字符和目标字符串第n个字符相等, 则dp[m][n]=dp[m-1][n-1],否则dp[m][n]=dp[m-1][n-1]+1;

4, 遍历规划后, 可以得到最终的结论