计算字符串距离

题目描述

对于两个字符串，允许两种代价为 1 的操作：替换某位置字符；删掉某个字符（增加字符也等价于对面删一次），求把第一个串变成第二个串的最少操作次数，即两串距离。第一行为测试组数 $n$ ，接下来 $n$ 行每行两个字符串（长度 ≤ 1000），逐组输出一行答案。样例：输入 3 / abcdefg abcdef / ab ab / mnklj jlknm，输出 1 / 0 / 4。

思路

令 $dp[i][j]$ 表示 a 前 i 个字符变成 b 前 j 个字符的最少代价，边界 $dp[i][0]=i$ 、 $dp[0][j]=j$ ；按 $a_i$ 与 $b_j$ 的关系转移：相同则白拿左上 $dp[i-1][j-1]$ ，否则在「替换」「删 $a_i$ 」「删 $b_j$ 」三种候选里取最小加 1。每行只依赖上一行，用一维数组加 diag 暂存左上角即可，复杂度 $O(mn)$ ，空间 $O(\min(m,n))$ 。

参考代码

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
31
32
33
34
35
36
37
38
39
40
41#!/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 03:53
# update_at: 2026-09-30 03:53

import sys


def distance(a: bytes, b: bytes) -> int:
    """滚动数组版编辑距离：dp[j] = a 的前 i 个字符变成 b 的前 j 个字符的最小代价。"""
    if len(a) < len(b):  # 增与删互为反向操作，距离对称；让内层循环跑在短串上
        a, b = b, a

    dp = list(range(len(b) + 1))  # 第 0 行：空的 a 补齐 b 的前 j 个字符，代价 j
    for i, ca in enumerate(a, 1):
        diag = dp[0]  # 左上角：a 的前 i-1 个字符对上 b 的前 0 个字符
        dp[0] = i     # 第 i 行边界：a 的前 i 个字符整段删空
        for j, cb in enumerate(b, 1):
            old = dp[j]  # 先取出「上」：它马上会被本行覆盖，留给下一格当「左上」
            # 相同则白拿左上角；不同则改一个字符，或删 / 增一个字符再走
            dp[j] = diag if ca == cb else min(diag, old, dp[j - 1]) + 1
            diag = old
    return dp[-1]


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))  # 测试数据的组数
    out: list[str] = []

    for _ in range(n):
        first, second = next(data), next(data)  # 直接按字节比对，免去逐字符解码
        out.append(str(distance(first, second)))

    print('\n'.join(out))


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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70/**
 * 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 08:25
 * update_at: 2026-10-05 08:25
 */
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXL = 1006; // 字符串长度 ≤ 1000，留一格存 '\0'

// dp[j] 表示把 a 的前 i 个字符变成 b 的前 j 个字符的最少操作次数
// 内层循环跑在较短串上，整体只用一行滚动数组
ll dp[MAXL];

char a_buf[MAXL];
char b_buf[MAXL];

// 计算 a 变成 b 的最少操作次数（编辑距离）
ll edit_distance(char *a, ll la, char *b, ll lb) {
    // 增与删互为反向操作，距离对称；让内层循环跑在短串上
    if (la < lb) {
        swap(a, b);
        ll t = la; la = lb; lb = t;
    }

    // 第 0 行：空 a 补齐 b 的前 j 个字符，代价 j
    for (ll j = 0; j <= lb; j++) {
        dp[j] = j;
    }

    for (ll i = 1; i <= la; i++) {
        ll diag = dp[0];   // 左上角：a 的前 i-1 个字符对上 b 的前 0 个字符
        dp[0] = i;          // 第 i 行边界：a 的前 i 个字符整段删空
        char ca = a[i - 1];
        for (ll j = 1; j <= lb; j++) {
            ll old = dp[j]; // 先取出「上」：它马上会被本行覆盖，留给下一格当「左上」
            if (ca == b[j - 1]) {
                dp[j] = diag; // 相同则白拿左上角
            } else {
                ll m = diag;
                if (old < m) m = old;
                if (dp[j - 1] < m) m = dp[j - 1];
                dp[j] = m + 1;
            }
            diag = old;
        }
    }
    return dp[lb];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int case_idx = 0; case_idx < n; case_idx++) {
        cin >> a_buf >> b_buf;
        ll la = strlen(a_buf);
        ll lb = strlen(b_buf);
        cout << edit_distance(a_buf, la, b_buf, lb) << "\n";
    }
    return 0;
}

目录

题目描述

思路

参考代码