最小编辑距离
#技术杂文#数据结构与算法 2025-02-26

最小编辑距离旨在定义两个字符串之间的相似度。

编辑距离

5e5afdda16b50a58aad923b4b513bd89.png

从 intention 到 execution 需要 1 次删除，3 次替换，和 1 次插入。

如果我们把三种操作的代价都记为 1 ，则其编辑距离为 5。

除此之外还有一种计算方法将替换的记为 2（即一次删除和一次插入），此时的总距离为 8。

最小编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(),m = word2.size();
        vector<vector<int>> dp(n+1, vector<int>(m+1));
        for(int i = 0;i <= n; ++i) dp[i][0] =  i;
        for(int j = 0;j <= m; ++j) dp[0][j] =  j;
        for(int i = 1;i<=n;++i){
            for(int j = 1;j<=m;++j){
                if(word1[i-1] == word2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = 1 +min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]));
            }
        }
        return dp[n][m];
    }
};

dp[i][j] 代表 word1 中前 i 个字符，变换到 word2 中前 j 个字符，最短需要操作的次数。

需要考虑 word1 或 word2 一个字母都没有，即全增加/删除的情况，所以预留 dp[0][j] 和 dp[i][0]。也就是图中左边的圆圈被划了一线的那个。

image20250226093515582.png

如果两个字符的最后一个字符相等，那么接下来就只需要考虑 [i-1] 前面的字符 和 [j-1] 前面的字符的高度相似性。

由于没有进行任何插入，删除，替换中的一个，不要进行距离加 1 操作。直接赋值就可以：dp[i][j] = dp[i-1][j-1]

image20250226101851345.png

如果当前两个单词的字符不相等，那就要进行插入，删除，替换中的一个，求三个操作的最小值，然后 + 1 即可。

dp[i-1][j-1]：替换之后，s1 的 x 变为 y，s1 和 s2 的最后一个字符就相等了，接下来就需要考虑 [i-1] 前面的字符 和 [j-1] 前面的字符的高度相似性

image20250226100755272.png

dp[i][j-1]：插入，在 s1 的 末尾添加 y 字符，s1 和 s2 的最后一个字符就相等了，接下来就需要考虑 [i] 前面的字符 和 [j - 1] 前面的字符的高度相似性

image20250226101447007.png

dp[i-1][j]：删除，把 s1 的 x 字符删除，接下来就需要考虑 [i-1] 前面的字符 和 [j] 前面的字符的高度相似性

image20250226101305809.png

参考链接

https://www.cnblogs.com/RioTian/p/12640881.html

https://www.bilibili.com/video/BV1sA411B73r/?spm_id_from=333.880.my_history.page.click