最长公共子序列

难度: Medium

给定两个字符串 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 仅由小写英文字符组成。

Submission

运行时间: 1016 ms

内存: 138.1 MB

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = dict()

        def dp(i, j):
            if (i, j) in memo:
                return memo[(i, j)]
            if i == -1 or j == -1:
                return 0
            if text1[i] == text2[j]:
                memo[(i, j)] = dp(i - 1, j - 1) + 1
            else:
                memo[(i, j)] = max(dp(i - 1, j), dp(i, j - 1))
            return memo[(i, j)]
        return dp(len(text1) - 1, len(text2) - 1)

Explain

这个题解采用了动态规划的方法。定义dp(i, j)为text1[0:i]和text2[0:j]的最长公共子序列的长度。如果text1[i]和text2[j]相同，说明这两个字符可以成为当前的最长公共子序列的一部分，因此dp(i, j) = dp(i-1, j-1) + 1；如果不同，则最长公共子序列要么在text1[0:i-1]和text2[0:j]中，要么在text1[0:i]和text2[0:j-1]中，因此dp(i, j) = max(dp(i-1, j), dp(i, j-1))。为了避免重复计算，使用memoization技术（通过字典memo存储已计算的结果）。

时间复杂度: O(m * n)

空间复杂度: O(m * n)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = dict()  # 用于存储已经计算过的dp值

        def dp(i, j):
            if (i, j) in memo:  # 如果结果已经在memo中，直接返回
                return memo[(i, j)]
            if i == -1 or j == -1:  # 边界情况，如果索引为-1，表示越界，返回0
                return 0
            if text1[i] == text2[j]:  # 如果字符匹配，递归计算左上角的值并加1
                memo[(i, j)] = dp(i - 1, j - 1) + 1
            else:  # 如果不匹配，取左边和上边的最大值
                memo[(i, j)] = max(dp(i - 1, j), dp(i, j - 1))
            return memo[(i, j)]
        return dp(len(text1) - 1, len(text2) - 1)  # 从最后一个字符开始计算

Explore

在定义dp(i, j)时使用索引-1作为边界条件是为了处理字符串为空的情况。这意味着当i或j为-1时，表示text1或text2中的一个字符串已经没有字符可比较，因此最长公共子序列长度为0。这种设置允许我们从索引0开始迭代，同时简化代码，因为索引从-1开始自然地处理了空字符串的情况，而不需要额外的初始化步骤。

当text1[i]与text2[j]不匹配时，我们需要找到不包含这两个不匹配字符中至少一个的最长公共子序列。dp(i-1, j)表示不考虑text1中的第i个字符（即text1[i]）时，text1和text2的最长公共子序列的长度；dp(i, j-1)则表示不考虑text2中的第j个字符（即text2[j]）时的最长公共子序列长度。比较这两者的最大值，我们可以得到在当前字符不匹配情况下，可能的最长公共子序列的长度。

使用字典memo作为存储的关键在于我们在计算dp(i, j)之前先检查它是否已经被计算并存储。如果已经存在于字典中，我们直接返回存储的结果，避免重复计算。这种方法比传统的动态规划表更为灵活，因为它只计算需要的dp值，而不是填充整个表格。特别是当一些dp值根本不需要被计算时，这种方法可以节省大量的空间和计算资源。

递归加记忆化的方法和非递归的动态规划方法各有优缺点。递归加记忆化通常更易于实现，代码更为直观和简洁，特别是在处理复杂问题时。然而，递归可能导致较深的调用栈，对于非常大的输入，可能会导致栈溢出。非递归的动态规划方法通常更稳定高效，因为它避免了递归调用的开销，并且可以更容易地进行空间优化，比如使用滚动数组。因此，选择哪种方法取决于具体问题的需求和环境限制。