最短编辑距离

算法笔记

给定两个字符串A和B，现在要将A经过若干操作变为B，可进行的操作有：

  1. 删除–将字符串A中的某个字符删除。
  2. 插入–在字符串A的某个位置插入某个字符。
  3. 替换–将字符串A中的某个字符替换为另一个字符。

现在请你求出，将A变为B至少需要进行多少次操作。

考虑这个问题时，我们可以想此问题：当字符串A中的第$i$个字符和字符串B的第$j$个字符对应时，执行的操作是多少呢？这样就需要一个二维数组去保存之前的所有状态。并且状态转移方程也很好想到：

当A[i]=B[j]时，f[i][j]=f[i-1][j-1]。

当A[i]!=B[j]时，综合考虑三种操作：f[i][j]=min(f[i-1][j],f[i-1][j-1],f[i][j-1])+1

分别对应删除、替换和插入操作。

具体实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
char s1[1001], s2[1001];
int n, m;
int f[1001][1001];
int main() {
    scanf("%d%s", &n, s1+1);
    scanf("%d%s", &m, s2+1);
    for(int i = 0; i <= n; ++i) f[i][0] = i;
    for(int i = 0; i <= m; ++i) f[0][i] = i;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            // 相等情况，不需要进行任何操作
            if(s1[i] == s2[j]) f[i][j] = f[i-1][j-1];
            else {
                f[i][j] = min(f[i-1][j], min(f[i-1][j-1],f[i][j-1]))+1;
            }
        }
    }
    printf("%d", f[n][m]);
    return 0;
}