1143. 最长公共子序列

题目

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

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

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

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

示例 2：

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

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

• 1 <= text1.length, text2.length <= 1000
• text1 和 text2 仅由小写英文字符组成。

解答

思路

子序列本质上也是 选或不选 的问题，和打家劫舍一样，我们从最后一个字符考虑。设两个字符串分别是 s, t，字符串的长度分别是 n, m。考虑最后一个字母，分别记为 x, y：

• 不选 x，不选 y
• 不选 x，选 y
• 选 x，不选 y
• 选 x，选 y

回溯三问：

• 当前操作：考虑 s[i] 和 t[j] 选或不选，有以上四种情况，递归的参数为 i, j
• 当前问题：s 的前 i 个字母和 t 的前 j 个字母的最长公共子序列的长度
• 它的子问题：
  • 不选 x，不选 y：s 的前 i - 1 个字母和 t 的前 j - 1 个字母的 LCS 长度
  • 不选 x，选 y：s 的前 i - 1 个字母和 t 的前 j 个字母的 LCS 长度
  • 选 x，不选 y：s 的前 i 个字母和 t 的前 j - 1 个字母的 LCS 长度
  • 选 x，选 y：s 的前 i - 1 个字母和 t 的前 j - 1 个字母的 LCS 长度 + 1

注意 都选和都不选 的子问题是一样的，唯一的区别在于 都选 要求 x == y。以及如果不选 x，选 y，看似是要求 y 和 LCS 的最后一个字符要一样，其实不然，它对应的 dfs(i - 1, j) 返回的只是单独看 s[0..i-1], t[0..j] 这两个字符串的 LCS 长度，与 t[j] 到底最后是否在 LCS 的结果中 无关。这里的 选 这个字可能有点误导。

递归关系式为：

$$\text{dfs}(i,j)=max(\text{dfs}(i-1,j),\text{dfs}(i,j-1),\text{dfs}(i-1,j-1))+(s[i]=t[j])$$

两个问题：

• 在 s[i] == t[j] 的时候，我们需要考虑只选其中一个这种情况吗
• 在 s[i] != t[j] 的时候，我们需要考虑二者都不选的情况吗

答案是否定的。我们先来看第一种情况，当 s[i] == t[j] 时：正常的应该是 dfs(i - 1, j - 1) + 1，而如果我们需要考虑只选其中一个，不妨设我们选了 t[j]，那么现在就需要确定：

$$\text{dfs}(i-1,j)>\text{dfs}(i-1,j-1)+1$$

如果 t[j] 在之后的 LCS 中没有被使用，那么 dfs(i - 1, j) 就等于是 dfs(i-1, j-1) 了，因此不妨设 t[j] 在最后的 LCS 中被采用了，它和 s[k] 相等，那么我们去掉 t[j], s[k] 得到的新的子序列长度应该满足：

$$\text{dfs}(i-1,j-1)>\text{dfs}(i-1,j-1)$$

而这是矛盾的，因此在 s[i] == t[j] 的时候，我们只需要考虑子问题 dfs(i - 1, j - 1) + 1 即可。

再来看第二个问题，当 s[i] != t[j] 时，考虑二者都不选，那么长度应该是 dfs(i - 1, j - 1)，显然它被 dfs(i - 1, j), dfs(i, j - 1) 所包含。

因此最终的简化递归关系式为：

$$\text{dfs}(i,j)=\{\begin{array}{rlrl}& \text{dfs}(i-1,j-1)+1& & s[i]=t[j]\\ & max(\text{dfs}(i-1,j),\text{dfs}(i,j-1))& & s[i]\ne t[j]\end{array}$$

记忆化搜索，状态个数乘以状态计算时间：

• 时间复杂度为 $O(mn)$
• 空间复杂度为 $O(mn)$

代码

class Solution:
    def longestCommonSubsequence(self, s: str, t: str) -> int:
        n = len(s)
        m = len(t)

        @cache
        def dfs(i, j):
            if i < 0 or j < 0:
                return 0
            
            if s[i] == t[j]:
                return dfs(i - 1, j - 1) + 1
            
            return max(dfs(i - 1, j), dfs(i, j - 1))
        
        return dfs(n - 1, m - 1)

思路：空间优化

改成递推公式：

$$f[i][j]=\{\begin{array}{lll}f[i-1][j-1]+1& & s[i]=t[j]\\ max(f[i-1][j],f[i][j-1])& & s[i]\ne t[j]\end{array}$$

避免负数下标：

$$f[i+1][j+1]=\{\begin{array}{lll}f[i][j]+1& & s[i]=t[j]\\ max(f[i][j+1],f[i+1][j])& & s[i]\ne t[j]\end{array}$$

根据递归关系式写出边界条件，都是 0。

代码

class Solution:
    def longestCommonSubsequence(self, s: str, t: str) -> int:
        n = len(s)
        m = len(t)

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

        for i, x in enumerate(s):
            for j, y in enumerate(t):
                if x == y:
                    f[i + 1][j + 1] = f[i][j] + 1
                else:
                    f[i + 1][j + 1] = max(f[i][j + 1], f[i + 1][j])
        
        return f[n][m]

思路：一维数组优化

从递推式看：

$$f[i][j]=\{\begin{array}{lll}f[i-1][j-1]+1& & s[i]=t[j]\\ max(f[i-1][j],f[i][j-1])& & s[i]\ne t[j]\end{array}$$

我们只需要知道 f[i][j] 的正上方、左上方、正左方这三个相邻数字即可。由于需要正左边的数字，因此只能从左往右计算，而如果我们从左往右计算，那么左上方这个数字会被之前的计算覆盖掉，因此我们用临时变量 pre 记录它。

代码

class Solution:
    def longestCommonSubsequence(self, s: str, t: str) -> int:
        n = len(s)
        m = len(t)

        f = [0] * (m + 1)

        for x in s:
            pre = f[0]
            for j, y in enumerate(t):
                tmp = f[j + 1] # 上一轮的 f[i][j]

                if x == y:
                    f[j + 1] = pre + 1
                else:
                    f[j + 1] = max(f[j + 1], f[j])
                
                pre = tmp

        return f[m]