企业官网建设流程全解析

题目概览

给你两个单词word1和word2，请返回将word1转换成word2所使用的最少操作数。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"输出：3解释：horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"输出：5解释：intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')

提示：

• 0 <= word1.length, word2.length <= 500
• word1和word2由小写英文字母组成

来源：72. 编辑距离 - 力扣（LeetCode）

解题分析

方法：动态规划

用 i 表示在 word1 遍历的位置，j 表示在 word2 遍历的位置，用二维数组 dp 存储结果，那么：

1. 当 word1 [ i ] == word2 [ j ] 时，说明不用操作，那么就看 i - 1 和 j - 1 的操作数 + 1，即 dp[ i ][ j ] = dp[ i-1 ][ j-1 ] + 1
2. 当 word1 [ i ] != word2 [ j ] 时，需要比较三个操作的步骤，
   替换就是看 dp[ i - 1 ][ j - 1] 的操作数，然后当前两个字母替换，即 dp[ i - 1 ][ j - 1 ] + 1；
   插入删除就是看 dp[ i - 1][ j ] 和 dp[ i ][ j - 1] 的操作数 + 1；
   那么最小操作步骤就是取三个的最小值，即：
   dp[ i ][ j ] = min {dp[ i - 1 ][ j - 1 ], dp[ i-1 ][ j ], dp[ i ][ j-1 ]} + 1

由于 i = 0 或 j = 0 时，无法获取 i - 1 或 j - 1 的值，因此我们可以将二维数组加一位，i = 0 或 j = 0 时填充空字符串和对应的字符串的比较结果，后续从 i = 1 和 j = 1 开始遍历。

时间复杂度：O(mn)
空间复杂度：O(mn)

class Solution { public int minDistance(String word1, String word2) { int m = word1.length(), n = word2.length(); int[][] dp = new int[m+1][n+1]; for (int i = 1; i <= m; ++i) { dp[i][0] = dp[i-1][0] + 1; } for (int j = 1; j <= n; ++j) { dp[0][j] = dp[0][j-1] + 1; } 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] = Math.min(dp[i-1][j], dp[i][j-1]) + 1; dp[i][j] = Math.min(dp[i][j], dp[i-1][j-1] + 1); } } } return dp[m][n]; } }