题解 | #牛群编号变更#

知识点

动态规划

解题思路

使用一个二维数组dp来保存状态转移矩阵，其中dp[i][j]表示将word1的前i个字符变更为word2的前j个字符所需要的最少操作次数。我们从空字符串开始进行操作，第一行和第一列分别表示将空字符串变更为word2的前j个字符和将word1的前i个字符变更为空字符串所需要的操作次数。

然后，我们使用两个嵌套循环遍历所有的字符组合，如果当前字符相同，则不需要进行操作，直接继承上一个状态的操作次数；否则，取插入、删除操作中的最小值并加一。

最终，返回dp[m][n]即可得到将s1变更为s2所需要的最少操作次数。

Java题解

import java.util.*;


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

        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 如果当前字符相同，则不需要进行操作，直接继承上一个状态的操作次数
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 否则，取插入、删除操作中的最小值，并加上相应的操作次数
                    dp[i][j] = 1 + Math.min(dp[i - 1][j],dp[i][j - 1]);
                }
            }
        }

        return dp[m][n];
    }
}