【例9.20】编辑距离

题目描述

给定字符串 $A$ 与 $B$ ，每次可以对 $A$ 执行三种操作之一：删除一个字符、插入一个字符、把一个字符改成另一个字符。求把 $A$ 变成 $B$ 所需的最少操作次数（即编辑距离）。输入第一行为 $A$ 、第二行为 $B$ ，两串长度均小于 2000；输出一个整数表示最少操作次数。样例：输入 sfdqxbw 与 gfdgw，输出 4。

思路

设 $f(i,j)$ 表示把 $A$ 的前 $i$ 个字符变成 $B$ 的前 $j$ 个字符的最少操作数，则 $f(i,j)$ 只由三种收尾决定：删除 $a_i$ 对应 $f(i-1,j)$ ，插入 $b_j$ 对应 $f(i,j-1)$ ，改写 $a_i$ 为 $b_j$ 对应 $f(i-1,j-1)$ （字符相同时零代价），取三者最小即可。边界为 $f(i,0)=i$ 、 $f(0,j)=j$ ，答案是 $f(n,m)$ 。由于第 $i$ 行只依赖第 $i-1$ 行和本行左邻，可以用滚动一维数组把空间压到 $O(m)$ ，时间复杂度 $O(nm)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 02:53
# update_at: 2026-09-30 02:53

import sys


def edit_distance(a: str, b: str) -> int:
    """把 a 变成 b 的最少操作数：滚动一维 DP，prev 恒指"上一行"。"""
    prev = list(range(len(b) + 1))       # a 空前缀：b[0..j-1] 只能逐个插入
    for i, ca in enumerate(a, 1):
        cur = [i] + [0] * len(b)         # b 空前缀：a[0..i-1] 只能逐个删除
        for j, cb in enumerate(b, 1):
            # 收尾三种选择：删掉 ca、插入 cb、把 ca 对上 cb（相同则零代价）
            cur[j] = prev[j - 1] if ca == cb else 1 + min(prev[j], cur[j - 1], prev[j - 1])
        prev = cur
    return prev[-1]


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    a, b = next(data).decode(), next(data).decode()
    print(edit_distance(a, b))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:44
 * update_at: 2026-10-05 07:44
 */
// main.cpp：编辑距离，滚动一维数组的前缀 DP。
#include <iostream>
#include <cstring>
#include <algorithm>

typedef long long ll;

const int MAXLEN = 2005;

char a[MAXLEN]; // 字符串 A，下标从 1 开始使用
char b[MAXLEN]; // 字符串 B，下标从 1 开始使用
int dp_prev[MAXLEN]; // dp_prev[j]：上一行（A 的前 i-1 个字符）变成 B 前 j 个字符的最少次数
int dp_cur[MAXLEN];  // dp_cur[j] ：当前行（A 的前 i 个字符）变成 B 前 j 个字符的最少次数

int main() {
    std::cin >> (a + 1) >> (b + 1);
    ll n = strlen(a + 1);
    ll m = strlen(b + 1);

    // 边界：A 为空前缀，B 的前 j 个字符只能逐个插入
    for (ll j = 0; j <= m; j++) {
        dp_prev[j] = j;
    }

    for (ll i = 1; i <= n; i++) {
        dp_cur[0] = i; // 边界：B 为空前缀，A 的前 i 个字符只能逐个删除
        for (ll j = 1; j <= m; j++) {
            if (a[i] == b[j]) {
                // 末位字符相同，直接对上，零代价
                dp_cur[j] = dp_prev[j - 1];
            } else {
                // 三种收尾取最小：删 a[i] / 插 b[j] / 改写 a[i]
                int best = std::min(dp_prev[j], dp_cur[j - 1]);
                best = std::min(best, dp_prev[j - 1]);
                dp_cur[j] = best + 1;
            }
        }
        // 当前行变成下一轮的上一行
        for (ll j = 0; j <= m; j++) {
            dp_prev[j] = dp_cur[j];
        }
    }

    std::cout << dp_prev[m] << std::endl;
    return 0;
}

【例9.20】编辑距离

目录

题目描述

思路

参考代码