最长公共子序列与字符串编辑距离

摘要

最长公共子序列（LCS）和编辑距离（Edit Distance）是字符串 DP 的两大基石，也是面试中最高频的 DP 题型之一。本文从 LCS 的二维状态推导出发，通过逐步分析”字符相等”和”字符不等”两种情况，建立起字符串 DP 的通用框架；再以编辑距离为主题，深入讲解三种操作（插入、删除、替换）如何映射到 DP 的三个转移方向；最后通过交织字符串（Interleaving String）展示字符串 DP 中”两个序列合并”的建模模式。

第 1 章从一维到二维：字符串 DP 的范式转变

1.1 从单序列到双序列

前面讲的 LIS 是单序列 DP——状态只依赖一个序列的下标 i，状态空间是一维的。

LCS 是双序列 DP——状态同时依赖两个序列的下标 i 和 j，状态空间是二维的。

这不只是维度的变化，而是建模方式的根本转变：

单序列 DP 中，每个状态描述”序列前 i 个元素的最优解”
双序列 DP 中，每个状态描述”两个序列各取前缀时的最优解”，即 s1[0..i-1] 和 s2[0..j-1] 的最优匹配结果

1.2 二维 DP 的通用框架

双序列 DP 的状态 dp[i][j] 通常表示：考虑了 s1 的前 i 个字符和 s2 的前 j 个字符时，某个目标的最优值。

状态转移的核心在于分析 s1[i-1] 和 s2[j-1] 是否相等（最后一对字符），以及对这对字符如何处理（匹配、插入、删除、替换……）。

第 2 章 LCS：最长公共子序列

2.1 问题定义

LeetCode 1143 - Longest Common Subsequence（中等）

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。

一个字符串的”子序列”是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

输入: text1 = "abcde", text2 = "ace"
输出: 3
解释: 最长公共子序列是 "ace"，它的长度为 3。

输入: text1 = "abc", text2 = "abc"
输出: 3

输入: text1 = "abc", text2 = "def"
输出: 0（没有公共子序列）

2.2 状态定义

dp[i][j] = text1[0..i-1]（前 i 个字符）和 text2[0..j-1]（前 j 个字符）的最长公共子序列长度。

注意：这里用 1-indexed 方式定义，dp[0][j] 和 dp[i][0] 表示某个字符串为空时的情况（LCS 长度为 0）。这种定义让初始化更自然。

2.3 状态转移方程

对于 dp[i][j]，分两种情况分析最后一对字符 text1[i-1] 和 text2[j-1]：

情况 1：text1[i-1] == text2[j-1]（字符相等）

这两个字符可以匹配，成为公共子序列的一部分。因此：

$d p [i] [j] = d p [i - 1] [j - 1] + 1$

含义：两个字符串各去掉最后一个字符（它们匹配），剩余部分的 LCS 长度加 1。

情况 2：text1[i-1] != text2[j-1]（字符不等）

这两个字符不能同时出现在公共子序列中（它们不相等）。有三种子情况：

丢弃 text1[i-1]，LCS 长度为 dp[i-1][j]
丢弃 text2[j-1]，LCS 长度为 dp[i][j-1]
同时丢弃（两个都不选），但这种情况被上面两种情况覆盖了

因此：

$d p [i] [j] = max (d p [i - 1] [j], d p [i] [j - 1])$

核心概念：LCS 转移方程的直觉

“字符相等”时，两个字符共同贡献一个长度，问题规模缩小为 (i-1, j-1)。 “字符不等”时，必须从两个序列中各自丢弃一个字符，取两种丢法中更好的结果。这两个情况合起来，穷举了所有可能的最后一步决策，保证了最优子结构。

2.4 初始化

dp[0][j] = 0 for all j（text1 为空，LCS 为 0）
dp[i][0] = 0 for all i（text2 为空，LCS 为 0）

Java 的 int[][] 默认初始化为 0，不需要显式设置。

2.5 完整实现

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    // dp[i][j] = text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度
    int[][] dp = new int[m + 1][n + 1];
 
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                // 最后一个字符匹配
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // 最后一个字符不匹配，丢掉其中一个，取最大值
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

时间复杂度： $O (mn)$ 空间复杂度： $O (mn)$ ，可用滚动数组优化到 $O (min (m, n))$

2.6 手工验证：`"abcde"` 和 `"ace"`

	a	c	e
""	0	0	0
a	1	1	1
b	1	1	1
c	1	2	2
d	1	2	2
e	1	2	3

dp[5][3] = 3。✅

2.7 LCS 的空间优化：滚动数组

dp[i][j] 只依赖 dp[i-1][j-1]、dp[i-1][j] 和 dp[i][j-1]，即只需要”上一行”加”当前行左侧”的值。

可以用一维数组 + 一个临时变量（记录左上角值）来优化：

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    // 保证 dp 数组对应较短的字符串，减少空间
    if (m < n) return longestCommonSubsequence(text2, text1);
 
    int[] dp = new int[n + 1];  // dp[j] 对应 text2[0..j-1]
 
    for (int i = 1; i <= m; i++) {
        int prev = 0;  // 记录 dp[i-1][j-1]（左上角值）
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];  // 保存将被覆盖的 dp[i-1][j]
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[j] = prev + 1;
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1]);
            }
            prev = temp;  // 更新左上角值
        }
    }
    return dp[n];
}

空间复杂度降至 $O (min (m, n))$ 。

第 3 章编辑距离：三方向转移

3.1 题目

LeetCode 72 - Edit Distance（困难）

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose  (删除 'r')
rose  -> ros   (删除 'e')

输入: word1 = "intention", word2 = "execution"
输出: 5

3.2 状态定义

dp[i][j] = 将 word1[0..i-1] 转换为 word2[0..j-1] 所需的最少操作数。

（与 LCS 相同的定义方式，1-indexed，空串对应下标 0。）

3.3 初始化

dp[i][0] = i：将 word1 的前 i 个字符变成空串，需要 i 次删除
dp[0][j] = j：将空串变成 word2 的前 j 个字符，需要 j 次插入

3.4 状态转移方程

情况 1：word1[i-1] == word2[j-1]

最后一对字符相同，不需要任何操作：

$d p [i] [j] = d p [i - 1] [j - 1]$

情况 2：word1[i-1] != word2[j-1]

最后一对字符不同，有三种操作选择：

操作	含义	转移来源
替换 `word1[i-1]` 为 `word2[j-1]`	两者都消耗一个字符	`dp[i-1][j-1] + 1`
删除 `word1[i-1]`	`word1` 少了一个字符，`word2` 不变	`dp[i-1][j] + 1`
插入 `word2[j-1]` 到 `word1` 末尾	`word1` 长度加 1 匹配 `word2[j-1]`，`word2` 少了一个字符	`dp[i][j-1] + 1`

取三者最小值：

$d p [i] [j] = 1 + min (d p [i - 1] [j - 1], d p [i - 1] [j], d p [i] [j - 1])$

核心概念：三种操作对应三个转移方向

替换 → 左上角（dp[i-1][j-1]）：两个字符各消耗一个

删除 word1 字符 → 上方（dp[i-1][j]）：word1 消耗一个字符

插入字符到 word1 → 左方（dp[i][j-1]）：word2 消耗一个字符这三个方向恰好对应了 DP 表格中的三个相邻位置，是双序列 DP 中最优美的转移关系之一。

3.5 完整实现

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
 
    // 初始化边界
    for (int i = 0; i <= m; i++) dp[i][0] = i;  // 删除 i 个字符
    for (int j = 0; j <= n; j++) dp[0][j] = j;  // 插入 j 个字符
 
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];  // 字符相同，无需操作
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j - 1],  // 替换
                    Math.min(
                        dp[i - 1][j],  // 删除 word1[i-1]
                        dp[i][j - 1]   // 插入 word2[j-1]
                    )
                );
            }
        }
    }
    return dp[m][n];
}

3.6 手工验证：`"horse"` → `"ros"`

	""	r	o	s
""	0	1	2	3
h	1	1	2	3
o	2	2	1	2
r	3	2	2	2
s	4	3	3	2
e	5	4	4	3

dp[5][3] = 3。✅

操作路径回溯（从右下角往左上角追踪决策）：

dp[5][3] = dp[4][2] + 1（删除 ‘e’）
dp[4][2] = dp[3][1] + 1（删除 ‘s’）
dp[3][1] = dp[2][1] + 1（替换 ‘r’ 为 ‘r’，不，实际是 dp[3][1] 来自 dp[2][0]+1=删除 ‘r’）

实际操作：horse → rorse → rose → ros（替换 ‘h’，删除 ‘r’，删除 ‘e’）= 3 步。

3.7 变体：最小 ASCII 删除和（LeetCode 712）

LeetCode 712 - Minimum ASCII Delete Sum for Two Strings

不是最小操作数，而是最小 ASCII 值总和（每次删除的是字符，代价是字符的 ASCII 值）。

状态定义一样，只是”删除”的代价变成了 ASCII 值：

dp[i][0] = word1[0..i-1] 中所有字符的 ASCII 总和（都删掉）
dp[0][j] = word2[0..j-1] 中所有字符的 ASCII 总和
字符相等时：dp[i][j] = dp[i-1][j-1]（两个字符都保留，不删）
字符不等时：dp[i][j] = min(dp[i-1][j] + ascii(word1[i-1]), dp[i][j-1] + ascii(word2[j-1]))

第 4 章交织字符串

4.1 题目

LeetCode 97 - Interleaving String（中等）

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交织（interleaving）组成的。

两个字符串 s 和 t 交织的定义与方法是：将 s 和 t 分成若干子字符串，同时保留它们的顺序，合并得到 s3。

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

4.2 建模分析

交织字符串要求：s3 的每个字符，要么来自 s1，要么来自 s2，且来自同一字符串的字符保持相对顺序。

关键约束：len(s1) + len(s2) == len(s3)（必要条件，否则直接返回 false）。

状态：dp[i][j] = s1[0..i-1] 和 s2[0..j-1] 能否交织组成 s3[0..i+j-1]。

转移方程：

s3 的第 i+j-1 个字符（s3[i+j-1]）要么来自 s1 的第 i 个字符，要么来自 s2 的第 j 个字符：

$d p [i] [j] = (d p [i - 1] [j] && s 1 [i - 1] == s 3 [i + j - 1]) OR (d p [i] [j - 1] && s 2 [j - 1] == s 3 [i + j - 1])$

初始化：

dp[0][0] = true（空串与空串交织结果是空串）
dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1]（s2 为空时，s3 只能由 s1 构成）
dp[0][j] = dp[0][j-1] && s2[j-1] == s3[j-1]

public boolean isInterleave(String s1, String s2, String s3) {
    int m = s1.length(), n = s2.length(), k = s3.length();
    if (m + n != k) return false;  // 长度不匹配，直接返回 false
 
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
 
    // 初始化第一列（s2 为空）
    for (int i = 1; i <= m; i++) {
        dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
    }
    // 初始化第一行（s1 为空）
    for (int j = 1; j <= n; j++) {
        dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
    }
 
    // 填表
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            char c = s3.charAt(i + j - 1);
            dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == c)  // 来自 s1
                    || (dp[i][j - 1] && s2.charAt(j - 1) == c); // 来自 s2
        }
    }
    return dp[m][n];
}

第 5 章字符串 DP 通用框架总结

5.1 双序列 DP 的通用模板

以上三道题（LCS、Edit Distance、Interleaving String）都遵循同一个框架：

状态定义：dp[i][j] = 处理 s1[0..i-1] 和 s2[0..j-1] 时的最优值

初始化：
    dp[0][0] = 基础情况
    dp[i][0] = 只用 s1 的前 i 个字符时的基础情况
    dp[0][j] = 只用 s2 的前 j 个字符时的基础情况

状态转移（核心）：
    case 1: s1[i-1] == s2[j-1]
        → dp[i][j] = f(dp[i-1][j-1])
    case 2: s1[i-1] != s2[j-1]
        → dp[i][j] = g(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

答案：dp[m][n]

不同题目的 f 和 g 不同，但框架完全一致。

5.2 三道题的对比

题目	目标	字符相等时	字符不等时
LCS	最长公共子序列长度	`dp[i-1][j-1] + 1`	`max(dp[i-1][j], dp[i][j-1])`
Edit Distance	最少编辑操作数	`dp[i-1][j-1]`	`1 + min(三方向)`
Interleaving String	是否可以交织	不适用（两个序列的字符来源不同）	OR 两种来源

5.3 LCS 与 Edit Distance 的深层联系

LCS 和 Edit Distance 之间有一个优美的数学关系：

设 lcs 为 s1 和 s2 的 LCS 长度，m = len(s1)，n = len(s2)。

将 s1 转化为 s2 的最少操作数（只考虑插入和删除，不考虑替换）等于：

$edit_distance_no_replace = (m - lcs) + (n - lcs) = m + n - 2 \times lcs$

含义：从 s1 中删除 m - lcs 个字符（LCS 以外的），再向 s2 插入 n - lcs 个字符（LCS 以外的）。

如果允许替换，替换比”先删除再插入”少一步，因此完整的编辑距离 ≤ m + n - 2 * lcs。

设计哲学：LCS 与编辑距离的等价性

当只允许插入和删除时，编辑距离 = m + n - 2 * lcs。这两道经典题在特定约束下完全等价，揭示了字符串匹配问题的内在一致性。

第 6 章高频字符串 DP 变体

6.1 LeetCode 583：两个字符串的删除操作

使两个字符串相同所需的最少删除步数。

等价于 m + n - 2 * lcs。

public int minDistance(String word1, String word2) {
    int lcs = longestCommonSubsequence(word1, word2);
    return word1.length() + word2.length() - 2 * lcs;
}

6.2 LeetCode 1035：不相交的线

在两个数组中，画若干条竖线连接相同的数字，要求线不相交（保持顺序），求最多能画多少条线。

本质上是 LCS：不相交 = 保持相对顺序 = 公共子序列的定义。

public int maxUncrossedLines(int[] nums1, int[] nums2) {
    // 等价于求 nums1 和 nums2 的 LCS 长度
    int m = nums1.length, n = nums2.length;
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

6.3 LeetCode 115：不同的子序列

给你一个字符串 s 和一个字符串 t，统计并返回在 s 的子序列中 t 出现的个数。

状态：dp[i][j] = s[0..i-1] 的子序列中，等于 t[0..j-1] 的个数。

转移：

s[i-1] == t[j-1]：可以选择这个字符匹配 → dp[i-1][j-1]，也可以不用这个字符去匹配 → dp[i-1][j]，共 dp[i-1][j-1] + dp[i-1][j]
s[i-1] != t[j-1]：只能不用这个字符 → dp[i-1][j]

public int numDistinct(String s, String t) {
    int m = s.length(), n = t.length();
    long[][] dp = new long[m + 1][n + 1];  // 用 long 防止溢出
    for (int i = 0; i <= m; i++) dp[i][0] = 1;  // t 为空，有 1 种子序列（空子序列）
 
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j];  // 不用 s[i-1] 匹配
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] += dp[i - 1][j - 1];  // 用 s[i-1] 匹配 t[j-1]
            }
        }
    }
    return (int) dp[m][n];
}

第 7 章字符串 DP 的空间优化技巧

7.1 为什么大多数字符串 DP 可以压缩到一维

以 LCS 为例，dp[i][j] 的转移只依赖：

dp[i-1][j-1]（左上角）
dp[i-1][j]（上方）
dp[i][j-1]（左方）

这意味着，计算第 i 行时，只需要第 i-1 行的数据。可以用一维数组 dp[j] 并额外用变量 prev 记录”左上角”值，将空间从 $O (mn)$ 压缩到 $O (n)$ 。

同理，Edit Distance 也可以类似优化。

7.2 一维优化的注意事项

字符串 DP 的一维优化需要仔细处理”左上角”值的更新顺序。每次更新 dp[j] 前，必须先保存旧的 dp[j]（作为下一轮的”左上角”值）：

// LCS 的一维空间优化骨架
for (int i = 1; i <= m; i++) {
    int prev = dp[0];  // 记录 dp[i-1][j-1]
    for (int j = 1; j <= n; j++) {
        int temp = dp[j];   // 保存 dp[i-1][j]（将被覆盖）
        if (s1[i-1] == s2[j-1]) dp[j] = prev + 1;
        else dp[j] = Math.max(dp[j], dp[j-1]);
        prev = temp;        // 更新左上角
    }
}

小结

本文构建了字符串双序列 DP 的完整框架：

LCS：字符相等 → dp[i-1][j-1] + 1；字符不等 → max(上, 左)。核心是”匹配还是丢弃”的二选一。
Edit Distance：字符相等 → dp[i-1][j-1]（无代价）；字符不等 → 1 + min(左上, 上, 左)。三方向对应三种编辑操作。
Interleaving String：判断型，每个字符来自哪个序列，OR 两种来源。

下一篇矩阵路径DP：网格出发的二维状态转移将从字符串 DP 转向二维网格 DP，探讨路径计数、障碍物处理和最小代价路径这三类经典问题。

汀的知识碎片

文章导航

05 最长公共子序列与字符串编辑距离

最长公共子序列与字符串编辑距离

摘要

第 1 章从一维到二维：字符串 DP 的范式转变

1.1 从单序列到双序列

1.2 二维 DP 的通用框架

第 2 章 LCS：最长公共子序列

2.1 问题定义

2.2 状态定义

2.3 状态转移方程

2.4 初始化

2.5 完整实现

2.6 手工验证：`"abcde"` 和 `"ace"`

2.7 LCS 的空间优化：滚动数组

第 3 章编辑距离：三方向转移

3.1 题目

3.2 状态定义

3.3 初始化

3.4 状态转移方程

3.5 完整实现

3.6 手工验证：`"horse"` → `"ros"`

3.7 变体：最小 ASCII 删除和（LeetCode 712）

第 4 章交织字符串

4.1 题目

4.2 建模分析

第 5 章字符串 DP 通用框架总结

5.1 双序列 DP 的通用模板

5.2 三道题的对比

5.3 LCS 与 Edit Distance 的深层联系

第 6 章高频字符串 DP 变体

6.1 LeetCode 583：两个字符串的删除操作

6.2 LeetCode 1035：不相交的线

6.3 LeetCode 115：不同的子序列

第 7 章字符串 DP 的空间优化技巧

7.1 为什么大多数字符串 DP 可以压缩到一维

7.2 一维优化的注意事项

小结

On this page

汀的知识碎片

文章导航

05 最长公共子序列与字符串编辑距离

最长公共子序列与字符串编辑距离

摘要

第 1 章 从一维到二维：字符串 DP 的范式转变

1.1 从单序列到双序列

1.2 二维 DP 的通用框架

第 2 章 LCS：最长公共子序列

2.1 问题定义

2.2 状态定义

2.3 状态转移方程

2.4 初始化

2.5 完整实现

2.6 手工验证："abcde" 和 "ace"

2.7 LCS 的空间优化：滚动数组

第 3 章 编辑距离：三方向转移

3.1 题目

3.2 状态定义

3.3 初始化

3.4 状态转移方程

3.5 完整实现

3.6 手工验证："horse" → "ros"

3.7 变体：最小 ASCII 删除和（LeetCode 712）

第 4 章 交织字符串

4.1 题目

4.2 建模分析

第 5 章 字符串 DP 通用框架总结

5.1 双序列 DP 的通用模板

5.2 三道题的对比

5.3 LCS 与 Edit Distance 的深层联系

第 6 章 高频字符串 DP 变体

6.1 LeetCode 583：两个字符串的删除操作

6.2 LeetCode 1035：不相交的线

6.3 LeetCode 115：不同的子序列

第 7 章 字符串 DP 的空间优化技巧

7.1 为什么大多数字符串 DP 可以压缩到一维

7.2 一维优化的注意事项

小结

On this page

第 1 章从一维到二维：字符串 DP 的范式转变

2.6 手工验证：`"abcde"` 和 `"ace"`

第 3 章编辑距离：三方向转移

3.6 手工验证：`"horse"` → `"ros"`

第 4 章交织字符串

第 5 章字符串 DP 通用框架总结

第 6 章高频字符串 DP 变体

第 7 章字符串 DP 的空间优化技巧