【python】Leetcode每日一题-最长公共子序列

【python】Leetcode每日一题-最长公共子序列

【题目描述】

给定两个字符串 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 。

【分析】

• 思路

  算法课dp的例题，状态转移方程：

  \[dp[i][j]=\begin{cases} dp[i-1][j-1]+1, & text1[i-1] = text2[j-1]\\ \max(dp[i-1][j],dp[i][j-1]), & text1[i-1]\neq text2[i-1] \end{cases} \]

  边界情况：

  空字符串与字符串最长公共子序列长度为零。

  原理：

  • $ text1[i-1] = text2[j-1] $时，很好理解，两个字符串最后一个字符相同，则最长公共子序列为最后一个字符（+1）与前面部分的和。
  • $ text1[i-1]\neq text2[i-1] $时，可以想象两个字符串并行进行匹配，相同的匹配，不相同的与空格匹配，则这时最长公共子序列为text1最后一个字符与空格匹配、或text2最后一个字符与空格匹配两者最大值。

• AC代码

  class Solution:
      def longestCommonSubsequence(self, text1: str, 
  text2: str) -> int:
          m1 = len(text1)
          m2 = len(text2)
          sum = [[0] * (m1+1) for i in range(m2+1)]
          for i in range(1, m2+1):
              for j in range(1, m1+1):
                  if text2[i-1] == text1[j-1]:
                      sum[i][j] = sum[i-1][j-1] + 1
                  else:
                      sum[i][j] = sum[i-1][j] if sum[i-1]
  [j] > sum[i][j-1] else sum[i][j-1]
          return sum[m2][m1]
  

• dalao的题解（自己前面解释可能会看不懂，可以看这个，-空格-）

  Click here