最长公共子序列

难度: 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 仅由小写英文字符组成。

注意：本题与主站 1143 题相同： https://leetcode-cn.com/problems/longest-common-subsequence/

Submission

运行时间: 170 ms

内存: 16.1 MB

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [0] * (len(text1) + 1)
        for a in text2:
            pre = 0
            for j, b in enumerate(text1):
                tmp = dp[j]
                dp[j] = pre + 1 if a == b else max(dp[j - 1], dp[j])
                pre = tmp
        return dp[-2]

Explain

该题解采用了动态规划的思想解决最长公共子序列的问题。动态规划数组 dp 用于记录到当前字符为止的最长公共子序列的长度。其中，dp[j] 代表考虑到 text1 的第 j 个字符和 text2 的当前字符为止的最长公共子序列长度。我们通过遍历 text2 中的每个字符，然后对于每个字符再遍历 text1 中的每个字符，如果两个字符相同，则 dp[j] 更新为 dp[j-1]（即前一个状态）加一；如果不同，则 dp[j] 更新为 dp[j] 和 dp[j-1] 中的较大值，以此保持 dp[j] 总是包含到当前位置为止的最长公共子序列长度。最后，dp[-2] 给出了整个序列的最长公共子序列的长度。

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

空间复杂度: O(n)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [0] * (len(text1) + 1)  # 初始化动态规划数组，长度为 text1 的长度加一
        for a in text2:  # 遍历 text2 中的每个字符
            pre = 0  # pre 用来记录更新 dp[j] 之前 dp[j] 的值
            for j, b in enumerate(text1):  # 遍历 text1 中的每个字符
                tmp = dp[j]  # 临时保存当前 dp[j]，以便下一轮使用
                dp[j] = pre + 1 if a == b else max(dp[j - 1], dp[j])  # 更新 dp[j]
                pre = tmp  # 更新 pre 为当前轮的 dp[j]
        return dp[-2]  # 返回结果，注意是 dp[-2] 而不是 dp[-1]

Explore

代码中的返回值 dp[-2] 实际上是一个错误。在正确的动态规划实现中，我们应该返回 dp[len(text1)]，即 dp[-1]，因为 dp 的长度是 len(text1) + 1。dp[i] 表示考虑 text1 的前 i 个字符和 text2 的整个字符序列时的最长公共子序列长度。因此，dp[len(text1)] 或 dp[-1] 才是包含 text1 所有字符时的最长公共子序列长度。

动态规划数组 dp 初始化为全0是因为在考虑任何字符之前，最长公共子序列的长度自然应为0。这种初始化确保了在进行第一次更新时，dp 数组正确地反映了没有任何公共子序列的情况。初始化为0对算法的正确性是必要的，它确保了算法从正确的基础开始累计子序列长度。对效率也有积极影响，因为它避免了需要额外的条件检查或处理边界情况的代码，使得实现更简洁高效。

在更新 dp[j] 的过程中，使用临时变量 pre 和 tmp 是为了正确保留上一轮的状态值。在一轮迭代中，如果直接使用 dp[j-1] 和 dp[j] 进行更新，那么 dp[j] 的更新将会影响到下一个 j 的 dp[j-1] 的值，因为 dp[j-1] 是下一次迭代中的 dp[j]。这会导致使用了已经被覆盖的错误状态，从而使得算法不能正确地计算出最长公共子序列。使用 pre 和 tmp 保留上一个状态和当前状态的值，使每次更新都基于正确的值，确保了算法的正确性。