最长公共子序列 (LCS):「模版」&「输出」

1143. 最长公共子序列

583. 两个字符串的删除操作

712. 两个字符串的最小ASCII删除和

 

「最长递增子序列」针对一个字符串,求出其最长递增子序列 (废话文学!!) 详细介绍可见 动态规划设计:最长递增子序列

「最长重复子数组」针对两个数组,求出其最长重复子数组 (子数组必须要连着) 详细介绍可见 最长重复子数组

而我们今天要介绍的是「最长公共子序列」,它是针对两个字符串,求出其最长公共子序列 (子序列可以不用连着)

模版归纳

首先结合题目 最长公共子序列,归纳总结出「最长公共子序列」问题的模版

毫无疑问这种类型的题目需要使用「DP」去解决!!这里给出一个例子s1 = "abcde", s2 = "ace",下面所有分析都围绕该样例展开

先给出dp[][]数组的定义:dp[i][j]表示子串s1[0..i]s2[0..j]最长公共子序列的长度

那么「状态转移方程」是什么呢?

为什么就是这样转移的呢?直接看下图:

5

那么「base case」是什么呢?

6

如上图粉色标记出来的就是 base case。橙色标记出来的是相等的情况,其余是不等的情况

完整模版

如何输出最长公共子序列

「最长公共子序列」问题基本都是要求返回一个最值即可,但是有时候面试官喜欢不按常理出牌,让你输出最长公共子序列

我们可以通过构造出来的二维dp数组来得到最长公共子序列。如下图所示,从最后一个点开始往左上角的方向遍历

7

如果s1[i] = s2[j],那么当前字符肯定在最长公共子序列中;否在我们就向左或者向上遍历

至于选择「向左」还是「向上」的方向,这就要和构造dp的时候联系起来。我们是挑了一个最大值,所以遍历的方向也是谁大就往谁的方向遍历

两个字符串的最小ASCII删除和

题目详情可见 两个字符串的最小ASCII删除和

其实这个题目的底层也是「最长公共子序列」,只是问法稍微变化了一点

「需要被删除的字符 = 原字符串 - 最长公共子序列」

结合这个题目我们把dp[][]数组的定义稍微改改:dp[i][j]表示子串s1[0..i]s2[0..j]最小 ASCII 删除和

那么「状态转移方程」是什么呢?(有点逆过程的意思!!!)

那么「base case」是什么呢?

8

如上图粉色标记出来的就是 base case,e表示 e 的 ASCII 值