题解 | #字符串最小变换次数#

本题为计算字符串的编辑距离

设两个字符串s1, s2长度分别为m, n， f(m, n)为将s1变换为s2的最小变换次数。

考虑s1的第m个字符s1[m-1]，s2的第n个字符s2[n-1]（下标从0开始），有两种情况：

1. s1[m-1] == s2[n-1]
   则最小变换次数为将s1的前m-1个字符变为s2的前n-1个字符的最小变换次数
   f(m, n) = f(m-1, n-1)
2. s1[m-1] != s2[n-1]
   根据题目的三种变换方式，将s1变为s2的最后一步可能是

• 将s1最后一个字符删掉 => 转化为求f(m-1, n)
• 将s2最后一个字符删掉 => 转化为求f(m, n-1)
• 将s1最后一个字符替换为s2最后一个字符 => 转换为求f(m-1, n-1)
  结果为三者中最小值 + 1
  f(m, n) = min{ f(m-1, n), f(m, n-1), f(m-1, n-1) } + 1

综合两种情况，f(m, n) 与f(m-1, n-1)、f(m, n-1)、f(m-1,n)有关，实现的过程就是填满如下二维表格的过程，每个格子的值可能来自其上方、左边或左上方的格子。另外，为了方便编写代码，添加了第0行和第0列：

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        char[] s1 = in.readLine().trim().toCharArray();
        char[] s2 = in.readLine().trim().toCharArray();
        int[][] dp = new int[s1.length+1][];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = new int[s2.length+1];
        }
        // 初始化第一行和第一列
        for (int i = 0; i <= s1.length; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= s2.length; j++) {
            dp[0][j] = j;
        }
        // 填其余格子
        for (int i = 1; i <= s1.length; i++) {
            for (int j = 1; j <= s2.length; j++) {
                if (s1[i-1] == s2[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                }
            }
        }
        System.out.println(dp[s1.length][s2.length]);
    }
}