题目

给定两个字符串 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 题相同：

解题思路分析

1、动态规划；时间复杂度O(n^2)，空间复杂度O(n^2)

func longestCommonSubsequence(text1 string, text2 string) int {
   n, m := len(text1), len(text2)
   dp := make([][]int, n+1)
   for i := 0; i < n+1; i++ {
      dp[i] = make([]int, m+1)
   }
   for i := 1; i <= n; i++ {
      for j := 1; j <= m; j++ {
         if text1[i-1] == text2[j-1] {
            dp[i][j] = dp[i-1][j-1] + 1
         } else {
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])
         }
      }
   }
   return dp[n][m]
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

2、动态规划；时间复杂度O(n^2)，空间复杂度O(n)

func longestCommonSubsequence(text1 string, text2 string) int {
   n, m := len(text1), len(text2)
   prev := make([]int, m+1)
   cur := make([]int, m+1)
   for i := 1; i <= n; i++ {
      for j := 1; j <= m; j++ {
         if text1[i-1] == text2[j-1] {
            cur[j] = prev[j-1] + 1
         } else {
            cur[j] = max(prev[j], cur[j-1])
         }
      }
      copy(prev, cur)
   }
   return cur[m]
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

3、动态规划；时间复杂度O(n^2)，空间复杂度O(n)

func longestCommonSubsequence(text1 string, text2 string) int {
   n, m := len(text1), len(text2)
   cur := make([]int, m+1)
   for i := 1; i <= n; i++ {
      pre := cur[0]
      for j := 1; j <= m; j++ {
         temp := cur[j]
         if text1[i-1] == text2[j-1] {
            cur[j] = pre + 1
         } else {
            cur[j] = max(cur[j], cur[j-1])
         }
         pre = temp
      }
   }
   return cur[m]
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

总结

Medium题目，题目同leetcode 1143.最长公共子序列；类似的题目还有：
leetcode 583.两个字符串的删除操作；
leetcode 712.两个字符串的最小ASCII删除和；
leetcode 1035.不相交的线；
leetcode 1048.最长字符串链