题解 | #牛群编号变更#

知识点：动态规划

思路：

这段代码实现了求解两个字符串的最小编辑距离。采用动态规划的思想，通过构建一个二维数组 f 作为动态规划表。表中的每个元素 f[i][j] 表示将 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最小编辑距离。

首先，初始化动态规划表的边界条件。 f[i][0] 表示将 word1 的前 i 个字符转换成空字符串所需的编辑距离，即 i；f[0][j] 表示将空字符串转换成 word2 的前 j 个字符所需的编辑距离，即 j。

然后，通过迭代计算动态规划表中的其他元素。对于每个 f[i][j]，有两种情况：

1. 如果 word1 的第 i 个字符和 word2 的第 j 个字符相等，那么在编辑的过程中不需要进行任何操作，此时 f[i][j] = f[i-1][j-1]。
2. 如果 word1 的第 i 个字符和 word2 的第 j 个字符不相等，那么可以进行三种操作：删除 word1 的第 i 个字符，插入 word2 的第 j 个字符，或者将 word1 的第 i 个字符替换为 word2 的第 j 个字符。因此 f[i][j] 可以由下面三者中的最小值得出：f[i-1][j] + 1：表示删除 word1 的第 i 个字符。f[i][j-1] + 1：表示插入 word2 的第 j 个字符。f[i-1][j-1] + 1：表示将 word1 的第 i 个字符替换为 word2 的第 j 个字符。

最后，返回 f[n][m]，即将 word1 转换成 word2 的最小编辑距离。

编程语言：java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param word1 string字符串
     * @param word2 string字符串
     * @return int整型
     */
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        int[][] f = new int[n + 1][m + 1];

        for (int i = 0; i <= n; i++) {
            f[i][0] = i;
        }

        for (int j = 0; j <= m; j++) {
            f[0][j] = j;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + 1;
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
                }
            }
        }

        return f[n][m];
    }
}