题解 | #牛群编号变更#
牛群编号变更
https://www.nowcoder.com/practice/9295f0f796b34793832710d5c939a619
知识点:动态规划
思路:
这段代码实现了求解两个字符串的最小编辑距离。采用动态规划的思想,通过构建一个二维数组 f
作为动态规划表。表中的每个元素 f[i][j]
表示将 word1
的前 i
个字符转换成 word2
的前 j
个字符所需的最小编辑距离。
首先,初始化动态规划表的边界条件。 f[i][0]
表示将 word1
的前 i
个字符转换成空字符串所需的编辑距离,即 i
;f[0][j]
表示将空字符串转换成 word2
的前 j
个字符所需的编辑距离,即 j
。
然后,通过迭代计算动态规划表中的其他元素。对于每个 f[i][j]
,有两种情况:
- 如果
word1
的第i
个字符和word2
的第j
个字符相等,那么在编辑的过程中不需要进行任何操作,此时f[i][j] = f[i-1][j-1]
。 - 如果
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]; } }