题目描述

[EN | CN]

给定两个字符串 text1text2,返回这两个字符串的最长公共子序列。

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

例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列,则返回 0

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 1 <= text1.length <= 1000
  • 1 <= text2.length <= 1000
  • 输入的字符串只含有小写英文字符。

解法 1:动规

复习动规三部曲:

  1. 找 DP 矩阵,要保存什么:

    对于一个维度为 (m, n) 的矩阵 dpmn 分别表示两个字符串的长度,那么矩阵中的元素 dp[i][j] 表示当我们取第一个字符串的前 i 个字符、第二个字符串的前 j 个字符时,他们的最长公共子序列。

  2. 找递推公式:

    对于矩阵元素 dp[i][j],如果第一个字符串的第 i 个字符与第二个字符串的第 j 个字符相等,那么直接等于 dp[i - 1][j - 1] + 1;如果不等,则等于不考虑这个字符串时的最大值,即 max(dp[i - 1][j], dp[i][j - 1])

  3. 找初始值:

    m=0 或者 n=0 时,动规矩阵元素为 0。

假设两个字符串的长度分别为 $m$、$n$,那么

  • 时间复杂度为 $O(mn)$,需要算 DP 矩阵;
  • 空间复杂度为 $O(mn)$,需要存 DP 矩阵,不过其实可以进一步优化为 $O(\min(m, n))$。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)

        dp  = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        return dp[-1][-1]
  • 执行用时:452 ms,在所有 Python3 提交中击败了 78.79% 的用户。
  • 内存消耗:21.5 MB,在所有 Python3 提交中击败了 6.25% 的用户。

解法 2:空间优化的动规

仔细观察动规矩阵,其实我们在计算 dp[i][j] 的时候最多就用到了 dp[i - 1][j]dp[i][j - 1]dp[i - 1][j - 1] 三个值,所以其实根本没有必要保存整个矩阵,而是保存当前行(三个值中的前两个)和 dp[i - 1][j - 1](三个值的最后一个)即可。

照着这样的思路,当计算 dp[i][j] 的时候,我们用一个缓存值 last 来保存 dp[i - 1][j - 1]

假设两个字符串的长度分别为 $m$、$n$,那么

  • 时间复杂度为 $O(mn)$,需要算 DP 矩阵;
  • 空间复杂度为 $O(\min(m, n))$,保存一个最短的列表。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)

        dp  = [0] * (n + 1)
        for i in range(1, m + 1):
            last = 0  # dp[i - 1][j - 1]
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[j], last = last + 1, dp[j]
                else:
                    dp[j], last = max(dp[j], dp[j - 1]), dp[j]

        return dp[-1]
  • 执行用时:432 ms,在所有 Python3 提交中击败了 90.77% 的用户。
  • 内存消耗:13.8 MB,在所有 Python3 提交中击败了 68.75% 的用户。