编辑距离

难度:

标签:

题目描述

给你两个单词 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 由小写英文字母组成

代码结果

运行时间: 112 ms, 内存: 17.5 MB

/*
 * 思路：类似于 Java 版本，我们使用动态规划求解最小编辑距离。
 * 这里我们使用 Stream 进行优化计算，主要利用 IntStream 进行索引的遍历。
 */
import java.util.stream.IntStream;
 
public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
 
        IntStream.rangeClosed(0, m).forEach(i -> dp[i][0] = i);
        IntStream.rangeClosed(0, n).forEach(j -> dp[0][j] = j);
 
        IntStream.rangeClosed(1, m).forEach(i -> {
            IntStream.rangeClosed(1, n).forEach(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 - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            });
        });
 
        return dp[m][n];
    }
}

解释

方法:

这是一道经典的动态规划题目。题解使用了带备忘录的递归方式实现动态规划。主要思路是，定义dp(i, j)表示将word1[0:i]转换为word2[0:j]的编辑距离，则dp(i, j)可以从以下三种情况转移而来：1. dp(i-1, j-1)，若当前字符word1[i]==word2[j]，则不需要操作；2. dp(i-1, j) + 1，相当于在word1[i]后面插入一个字符word2[j]；3. dp(i, j-1) + 1，相当于在word1[i]后面删除一个字符；4. dp(i-1, j-1) + 1，将word1[i]替换为word2[j]。递归公式为dp(i, j) = min(dp(i-1, j-1), dp(i-1, j)+1, dp(i, j-1)+1, dp(i-1, j-1)+1)。边界条件为当i=-1时，相当于word1为空，需要插入j+1个字符，dp(i, j)=j+1；当j=-1时，相当于word2为空，需要删除i+1个字符，dp(i, j)=i+1。为了避免重复计算，使用了备忘录memo存储已计算过的dp值。

时间复杂度:

O(mn)

空间复杂度:

O(mn)

代码细节讲解

🦆

在递归函数`dp(i, j)`中，为什么选择`i == -1`和`j == -1`作为基准情况，而不是`i == 0`或`j == 0`？

▷

在`dp(i, j)`函数中，选择`i == -1`和`j == -1`作为基准情况用于表示字符串`word1`或`word2`已经完全处理完毕（即已经为空）。当`i == -1`时，意味着要将一个空的`word1`转换为`word2[0:j]`，这需要添加`j+1`个字符。同样，当`j == -1`时，意味着将`word1[0:i]`转换为一个空的`word2`，这需要删除`i+1`个字符。这些基准情况是边界条件，提供了递归过程中必要的停止点。如果选择`i == 0`或`j == 0`作为基准情况，虽然可以表示单个字符与空字符串的关系，但不足以完整表达整个字符串与空字符串之间的转换关系。

🦆

题解中的递归公式`dp(i, j) = min(dp(i-1, j-1), dp(i-1, j)+1, dp(i, j-1)+1, dp(i-1, j-1)+1)`似乎存在重复，是否有错误？正确的递归公式应该是什么样的？

▷

确实，题解中的公式存在重复，`dp(i-1, j-1)`被重复了两次。正确的递归公式应该是`dp(i, j) = min(dp(i-1, j-1) + (1 if word1[i] != word2[j] else 0), dp(i-1, j) + 1, dp(i, j-1) + 1)`。这里，如果`word1[i]`和`word2[j]`字符不同，则`dp(i-1, j-1)`需要增加1来表示替换操作；否则，如果字符相同，则不增加额外成本。

🦆

在处理字符替换的情况时，如果`word1[i]`与`word2[j]`不同，为什么选择使用`dp(i-1, j-1) + 1`而不是直接考虑其它操作？

▷

当`word1[i]`与`word2[j]`不同，选择使用`dp(i-1, j-1) + 1`是因为这表示最直接的替换操作——即将`word1[i]`直接替换成`word2[j]`，从而使两个字符串在这一位置匹配。这是一种高效的方式来处理字符不匹配的情况，因为它直接解决了不匹配的问题，而不是通过插入或删除间接调整。插入或删除虽然也可以达到目的，但它们通常需要更多步骤或更复杂的操作来实现两字符串的匹配。

相关问题

相隔为 1 的编辑距离

两个字符串的删除操作

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步可以删除任意一个字符串中的一个字符。

示例 1：

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

示例 2:

输入：word1 = "leetcode", word2 = "etco"
输出：4

提示：

1 <= word1.length, word2.length <= 500
word1 和 word2 只包含小写英文字母

两个字符串的最小ASCII删除和

给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。

示例 1:

输入: s1 = "sea", s2 = "eat"
输出: 231
解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
在 "eat" 中删除 "t" 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例 2:

输入: s1 = "delete", s2 = "leet"
输出: 403
解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。

提示:

0 <= s1.length, s2.length <= 1000
s1 和 s2 由小写英文字母组成

不相交的线

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：

nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

示例 1：

输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。 
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。

示例 2：

输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3

示例 3：

输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2

提示：

1 <= nums1.length, nums2.length <= 500
1 <= nums1[i], nums2[j] <= 2000

简化路径矩阵置零