问题

Levenshtein Distance，一般称为编辑距离（Edit Distance，Levenshtein Distance只是编辑距离的其中一种）或者莱文斯坦距离，算法概念是俄罗斯科学家弗拉基米尔·莱文斯坦（Levenshtein · Vladimir I）在1965年提出。此算法的概念很简单：Levenshtein Distance指两个字串之间，由一个转换成另一个所需的最少编辑操作次数，允许的编辑操作包括：

  • 将其中一个字符替换成另一个字符（Substitutions）。、
  • 插入一个字符（Insertions）。
  • 删除一个字符（Deletions）。
image-20251117195049889

问题分析

看上去就像是动态规划

那么考虑子问题，从 a[1...i] 到 b[1.....j]的编辑距离

那么我们就可以考虑这样一个状态变量

  • 设 dp[i][j] 表示将字符串 a 的前 i 个字符（a[0..i-1]）转换为字符串 b 的前 j 个字符（b[0..j-1]）所需的最少操作次数。

如何考虑状态转移方程呢？

如果 a[i] = b[j]，则相当于把 a 的前 i - 1个字符修改为 b 的前 j - 1 个字符的操作次数

这是显然的，因为末尾元素相等，所以不需要修改

所以，若 a[i-1] == b[j-1]，当前字符相同，无需操作，则dp[i][j] = dp[i-1][j-1]

如果 a[i] != b[j]，那么我们就需要修改 a 的第 i个字符

就需要考虑吧，修改，删除，插入的最小值了

所以，若 a[i-1] != b[j-1]，也就是当前字符不同。需要编辑，取三种操作的最小值加 1

  • 替换：将 a[i-1] 改为 b[j-1]，操作数 = dp[i-1][j-1] + 1
  • 删除：删除 a[i-1]，操作数 = dp[i-1][j] + 1
  • 插入：在 a[i-1] 后插入 b[j-1]，操作数 = dp[i][j-1] + 1

即：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

就有状态转移方程

image-20251117200138657

最后考虑边界条件

  • 当 j=0 时（目标字符串为空）：需要删除 a 的前 i 个字符，因此 dp[i][0] = i
  • 当 i=0 时（源字符串为空）：需要插入 b 的前 j 个字符，因此 dp[0][j] = j
image-20251117200152450

模板代码

模板题：https://www.luogu.com.cn/problem/P2758

Java

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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.next();  // 源字符串
        String b = scanner.next();  // 目标字符串
        int la = a.length();        // 源字符串长度
        int lb = b.length();        // 目标字符串长度

        // 创建DP表，维度为 (la+1) x (lb+1)
        int[][] f = new int[la + 1][lb + 1];

        // 初始化：源字符串转为空字符串（删除操作）
        for (int i = 1; i <= la; i++) {
            f[i][0] = i;
        }
        // 初始化：空字符串转为目标字符串（插入操作）
        for (int i = 1; i <= lb; i++) {
            f[0][i] = i;
        }

        // 填充DP表
        for (int i = 1; i <= la; i++) {
            for (int j = 1; j <= lb; j++) {
                // 当前字符相同，直接继承前序状态
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    f[i][j] = f[i - 1][j - 1];
                } else {
                    // 当前字符不同，取三种操作的最小值+1
                    f[i][j] = Math.min(
                        Math.min(f[i - 1][j],    // 删除操作
                                 f[i][j - 1]),   // 插入操作
                        		f[i - 1][j - 1] // 替换操作
                    ) + 1;
                }
            }
        }

        // 输出最终结果：整个a转为整个b的最少操作数
        System.out.println(f[la][lb]);
    }
}

C++

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
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    int la = a.size();
    int lb = b.size();
    
    // 创建DP表
    int f[la + 1][lb + 1];
    
    // 初始化：源字符串转为空字符串（删除操作）
    for (int i = 1; i <= la; ++i) {
        f[i][0] = i;
    }
    // 初始化：空字符串转为目标字符串（插入操作）
    for (int i = 1; i <= lb; ++i) {
        f[0][i] = i;
    }
    
    // 填充DP表
    for (int i = 1; i <= la; ++i) {
        for (int j = 1; j <= lb; ++j) {
            if (a[i - 1] == b[j - 1]) {
                f[i][j] = f[i - 1][j - 1];
            } else {
                f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;
            }
        }
    }
    
    cout << f[la][lb] << endl;
    return 0;
}

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
a = input().strip()
b = input().strip()
la = len(a)
lb = len(b)

# 创建DP表（(la+1)行，(lb+1)列）
f = [[0] * (lb + 1) for _ in range(la + 1)]

# 初始化：源字符串转为空字符串（删除操作）
for i in range(1, la + 1):
    f[i][0] = i

# 初始化：空字符串转为目标字符串（插入操作）
for i in range(1, lb + 1):
    f[0][i] = i

# 填充DP表
for i in range(1, la + 1):
    for j in range(1, lb + 1):
        if a[i - 1] == b[j - 1]:
            f[i][j] = f[i - 1][j - 1]
        else:
            # 取三种操作的最小值加1
            f[i][j] = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1

print(f[la][lb])

例题

问题

洛谷 P1279 字串距离

P1279 字串距离

题目描述

设有字符串 X，我们称在 X 的头尾及中间插入任意多个空格后构成的新字符串为 X 的扩展串，如字符串 X 为$\verb!abcbcd!$，则字符串 $\verb!abcb␣cd!$，$\verb!␣a␣bcbcd␣!$ 和 $\verb!abcb␣cd␣!$ 都是 X 的扩展串，这里 $\verb!␣!$ 代表空格字符。

如果 A1 是字符串 A 的扩展串，B1 是字符串 B 的扩展串，A1 与 B1 具有相同的长度，那么我们定义字符串 A1 与 B1 的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的 ASCII 码的差的绝对值，而空格字符与其他任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为 0。在字符串 A、B 的所有扩展串中，必定存在两个等长的扩展串 A1，B1，使得 A1 与 B1 之间的距离达到最小，我们将这一距离定义为字符串 A，B 的距离。

请你写一个程序，求出字符串 A，B 的距离。

输入格式

输入文件第一行为字符串 A ，第二行为字符串 B。A，B 均由小写字母组成且长度均不超过 2000。第三行为一个整数 K(1 ≤ K ≤ 100)，表示空格与其他字符的距离。

输出格式

输出文件仅一行包含一个整数，表示所求得字符串 A, B 的距离。

输入输出样例 #1

输入 #1

1
2
3
>cmc
>snmn
>2

输出 #1

1
>10

问题分析

首先，这道题本质上还是，求两个字符串通过 “特定操作” 达到 “匹配状态” 的最小代价（距离）

题目要求 “两个等长扩展串的最小距离”，其实可以理解为：

  • 给字符串 A、B 插入任意空格（扩展），让它们长度相同；
  • 对应位置字符计算距离（非空格算 ASCII 差绝对值，空格与非空格算 K，空格与空格算 0）；
  • 找到总距离最小的对齐方式，这个总距离就是答案。

那么我们就可以观察，有这样的三种情况

  • A 的某个字符和 B 的某个字符对齐了已经，那么这样就都不需要插入空格
  • A 的某个字符 和 B串 中的 某个空格 对齐，就需要给 B 插空格
  • A 的某个空格 和 B串 的某个字符 对齐，就需要给 A 插空格

空格与空格对齐无需考虑，因为这种情况的距离是 0，但它等价于 “同时给 A 和 B 插空格”，不会改变总距离，所以不考虑

考虑动态规划

设 dp[i][j] 表示，字符串 A 的前 i 个字符（A [0..i-1]）和 字符串 B 的前 j 个字符（B [0..j-1]），通过扩展得到等长串后的最小距离。

对于 i>0 且 j>0，根据上面写的 三种对齐情况 可以推导状态转移方程：

  • A [i-1] 和 B [j-1] 对齐

    都不插空格

    距离 = 之前的最小距离（dp[i-1][j-1]） + 两个字符的 ASCII 差绝对值；

  • A [i-1] 和 空格 对齐

    给 B 插空格

    距离 = 之前的最小距离（dp[i-1][j]） + K（空格与非空格的距离）；

  • 空格 和 B [j-1] 对齐

    给 A 插空格

    距离 = 之前的最小距离（dp[i][j-1]） + K；

dp[i][j] 取这三种情况的最小值，即： $$ dp[i][j] = \min \begin{cases} dp[i-1][j-1] + |ord(A[i-1]) - ord(B[j-1])| & \text{字符对字符} \\ dp[i-1][j] + K & \text{字符对空格} \\ dp[i][j-1] + K & \text{空格对字符} \end{cases} $$ 确定边界

边界情况是 “其中一个字符串为空”，此时只能通过插空格对齐：

  • 当 j=0（B 为空串）：A 的前 i 个字符必须都和空格对齐，每个字符的距离是 K，所以 dp[i][0] = dp[i-1][0] + K（初始 dp[0][0] = 0）；
  • 当 i=0（A 为空串）：B 的前 j 个字符必须都和空格对齐，每个字符的距离是 K，所以 dp[0][j] = dp[0][j-1] + K。

分析复杂度

  • 时间复杂度：O(n*m)，n 是 A 的长度，m 是 B 的长度（双重循环填充 DP 表）；
  • 空间复杂度：O(n*m)，DP 表是 (n+1)×(m+1) 的二维数组。

注意，容易忘记 dp[0][0] = 0，空串对齐空串距离为 0

代码

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
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String A = br.readLine();
        String B = br.readLine();
        int K = Integer.parseInt(br.readLine());

        int n = A.length();
        int m = B.length();

        int[][] dp = new int[n + 1][m + 1];

        // 初始化边界
        // A的前i个字符对齐空串B（全空格）
        for (int i = 1; i <= n; i++) dp[i][0] = dp[i - 1][0] + K;

        // B的前j个字符对齐空串A（全空格）
        for (int i = 1; i <= m; i++) dp[0][i] = dp[0][i - 1] + K;

        for (int i = 1; i <= n; i++) {
            char aChar = A.charAt(i - 1);
            for (int j = 1; j <= m; j++) {
                char bChar = B.charAt(j - 1);

                // 情况1：A[i-1]与B[j-1]对齐（非空格对非空格）
                int costChar = dp[i - 1][j - 1] + Math.abs(aChar - bChar);

                // 情况2：A[i-1]与空格对齐（给B插空格）
                int costASpace = dp[i - 1][j] + K;

                // 情况3：空格与B[j-1]对齐（给A插空格）
                int costBSpace = dp[i][j - 1] + K;

                dp[i][j] = Math.min(Math.min(costChar, costASpace), costBSpace);
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        pw.println(dp[n][m]);
        pw.flush();
    }
}

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
A = input().strip()
B = input().strip()
K = int(input())

n, m = len(A), len(B)

dp = [[0] * (m + 1) for _ in range(n + 1)]

# 边界条件1：A的前i个字符对齐空串B
for i in range(1, n + 1):
    dp[i][0] = dp[i-1][0] + K

# 边界条件2：B的前j个字符对齐空串A
for j in range(1, m + 1):
    dp[0][j] = dp[0][j-1] + K

for i in range(1, n + 1):
    for j in range(1, m + 1):
        # 三种对齐情况的代价
        cost_char = dp[i-1][j-1] + abs(ord(A[i-1]) - ord(B[j-1]))
        cost_a_space = dp[i-1][j] + K
        cost_b_space = dp[i][j-1] + K
        # 取最小值
        dp[i][j] = min(cost_char, cost_a_space, cost_b_space)

print(dp[n][m])
image-20251118141107984