LeetCode刷题之HOT100之编辑距离

吃了一份扬州炒饭，等会还要去喝点酒，今天室友生日，下午上课我才反应过来。先做道题再说。
2024/6/8 昨天去喝酒去了，这道题没有做。大概喝到凌晨一点，看了会《地下室手记》，简单洗漱后上床准备休憩。辗转无眠，凌晨五点 天见白，遂去旗山湖走了一圈。放几张风景照。

图一、渔人撑篙打渔，好不快意

图二 、旗山准备醒来

图三 、莲花睡在上面宁静、恬适

图四、湖光山色，甚美

Anyway，景色看过，那么接下来就做做题。

1、题目描述

2、逻辑分析

这题以前是hard啊，现在反而被降级了。我是说怎么看不懂，题解也有些看不懂啊。GPT如是说：
算法原理：编辑距离是衡量两个字符串差异的一种指标，表示通过插入、删除和替换操作将一个字符串转换成另一个字符串所需要的最少编辑次数。
步骤：

1. 初始化：
   如果其中一个字符串为空，那么编辑距离就等于非空字符串的长度，因为需要将空字符串填充成另一个字符串，这需要进行与另一个字符串长度相等的插入操作。

2. 动态规划：
   这个问题可以使用动态规划（DP）来解决。DP 数组 D 的每个元素 D[i][j] 表示 word1 的前 i 个字符和 word2 的前 j 个字符之间的最小编辑距离。
   初始化DP数组的边界条件：当 word2 为空时，word1 需要删除所有字符才能变为空串，所以 D[i][0] 被初始化为 i 。同理，D[0][j] 被初始化为 j 。

3. 填充 DP 数组：
   对于D[i][j] ，有三种可能的操作：
   删除：将 word1 的第 i 个字符删除，此时 D[i][j] 依赖于 D[i-1][j]，需要加1表示进行了一次删除操作。
   插入：在 word1 的前 i 个字符后插入 word2 的第 j 个字符，此时 D[i][j] 依赖于D[i][j-1]，需要加1表示进行了一次插入操作。
   替换：如果word1的第i个字符和word2的第 j 个字符不同，则将word1的第i个字符替换为word2的第 j 个字符，此时D[i][j]依 赖于 D[i-1][j-1]，需要加1表示进行了一次替换操作；如果两者相同，则不需要替换，D[i][j]就等于D[i-1][j-1]。
   D[i][j]取上述三种操作中结果最小的那个。

GPT给出得已经较为完备，现在还没懂的原因就是，没有真正的去思考具体步骤。

去csdn找到一个比较清晰的版本，放下图，链接也放过来：详解编辑距离。

相关代码说明

// 删除操作
                int left = dp[i - 1][j] + 1;
                // 插入操作 
                int up = dp[i][j - 1] + 1;
                // 替换操作的基础值
                int left_up = dp[i - 1][j - 1];
                // 如果字符不同，需要替换，加1
                if(word1.charAt(i - 1) != word2.charAt(j - 1)){
                    left_up += 1;
                }
                // 取三种操作中的最小值
                dp[i][j] = Math.min(left, Math.min(up, left_up));

那么我们以一个例子来说明具体过程：
如两个单词分别为 dog 和 doge。初始化行和列。

我们需要知道？上的值
由于’d’ = ‘d’，两字符相等，我们取三的点最小值即为Math.min(1+1, Math.min( 1+1, 0+0))= 0

下面我们继续，向右遍历：‘d’ != ‘o’,Math.min(0+1, Math.min( 2+1, 1+1)) = 1

以此类推可以得到最终结果

下面代码演示

3、代码演示

public int minDistance(String word1, String word2) {
// word1的长度和world2的长度 
int n = word1.length();  
int m = word2.length();
// 如果有一个字符串为空，则编辑距离等于非空字符串的长度
if(n * m == 0){
return n + m ;
}
// 初始化DP数组，大小为(n+1) x (m+1)
int [][] dp = new int [n + 1][m + 1];
// 初始化DP数组的边界条件 
// 当word2为空时，需要删除word1的所有字符
for(int i = 0; i < n + 1; i++){
dp[i][0] = i;
}
// 当word1为空时，需要插入word2的所有字符 
for(int j = 0; j < m + 1; j++){
dp[0][j] = j;
}
// 填充DP数组的其他元素
for(int i = 1; i < n + 1; i++){
for(int j = 1; j < m + 1; j++){
// 删除操作
int left = dp[i - 1][j] + 1;
// 插入操作 
int up = dp[i][j - 1] + 1;
// 替换操作的基础值
int left_up = dp[i - 1][j - 1];
// 如果字符不同，需要替换，加1
if(word1.charAt(i - 1) != word2.charAt(j - 1)){
left_up += 1;
}
// 取三种操作中的最小值
dp[i][j] = Math.min(left, Math.min(up, left_up));
}
}
// 返回编辑距离
return dp[n][m];        
}

4、复杂度分析

• 时间复杂度：O(mn)，两个循环需要的时间，n为world1的长度，m为world2的长度。
• 空间复杂度：O(mn)，需要一个二维数组来保存中间值

5、总结

这题看着不简单，理解起来也确实不简单哈哈，不过最后还是理解了七七八八。Anyway，我要去吃午饭了，这道题做了好久，再见！