1143. 最长公共子序列

1143. 最长公共子序列 #

  • 标签:字符串、动态规划
  • 难度:中等

题目大意 #

描述:给定两个字符串 text1text2

要求:返回两个字符串的最长公共子序列的长度。如果不存在公共子序列,则返回 0

说明

  • 子序列:原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
  • 公共子序列:两个字符串所共同拥有的子序列。
  • $1 \le text1.length, text2.length \le 1000$。
  • text1text2 仅由小写英文字符组成。

示例

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

解题思路 #

思路 1:动态规划 #

1. 定义状态 #

定义状态 dp[i][j] 表示为:前 i 个字符组成的字符串 str1 与前 j 个字符组成的字符串 str2 的最长公共子序列长度为 dp[i][j]

2. 状态转移方程 #

双重循环遍历字符串 text1text2,则状态转移方程为:

  • 如果 text1[i - 1] == text2[j - 1],则说明找到了一个公共字符,此时 dp[i][j] = dp[i - 1][j - 1] + 1
  • 如果 text1[i - 1] != text2[j - 1],则 dp[i][j] 需要考虑以下两种情况,取两种情况中最大的那种:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    • text1i - 1 个字符组成的字符串 str1text2j 个字符组成的 str2 的最长公共子序列长度,即 dp[i - 1][j]
    • text1i 个字符组成的字符串 str1text2j - 1 个字符组成的 str2 的最长公共子序列长度,即 dp[i][j - 1]
3. 初始化 #

初始状态下,默认前 i 个字符组成的字符串 str1 与前 j 个字符组成的字符串 str2 的最长公共子序列长度为 0,即 dp[i][j] = 0

4. 最终结果 #

根据状态定义,最后输出 dp[sise1][size2](即 text1text2 的最长公共子序列长度)即可,其中 size1size2 分别为 text1text2 的字符串长度。

思路 1:动态规划代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        size1 = len(text1)
        size2 = len(text2)
        dp = [[0 for _ in range(size2 + 1)] for _ in range(size1 + 1)]
        for i in range(1, size1 + 1):
            for j in range(1, size2 + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        return dp[size1][size2]

思路 1:复杂度分析 #

  • 时间复杂度:$O(n^2)$。两重循环遍历的时间复杂度是 $O(n^2)$,所以总的时间复杂度为 $O(n^2)$。
  • 空间复杂度:$O(n^2)$。用到了二维数组保存状态,所以总体空间复杂度为 $O(n^2)$。
本站总访问量  次  |  您是本站第  位访问者