一、问题描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。 一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

二、方案一：动态规划

1、思路

动态规划是解决这类问题的经典方法。我们可以使用一个二维数组 dp，其中 dp[i][j] 表示字符串 text1 的前 i 个字符与字符串 text2 的前 j 个字符的最长公共子序列的长度。

• 如果 text1[i - 1] == text2[j - 1]，那么 dp[i][j] = dp[i - 1][j - 1] + 1。
• 否则，dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。

2、代码实现

func longestCommonSubsequence(text1 string, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            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[m][n]
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(m * n)，其中 m 和 n 分别是字符串 text1 和 text2 的长度。
• 空间复杂度：O(m * n)，用于存储动态规划表。

三、方案二：优化空间复杂度

1、思路

在方案一中，我们使用了二维数组来存储中间结果。实际上，我们只需要存储当前行和上一行的数据即可，因此可以将空间复杂度优化到 O(n)。

2、代码实现

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

3、复杂度分析

• 时间复杂度：O(m * n)，其中 m 和 n 分别是字符串 text1 和 text2 的长度。
• 空间复杂度：O(n)，因为我们只需要存储当前行和上一行的数据。

四、总结

方案	时间复杂度	空间复杂度
方案一	O(m * n)	O(m * n)
方案二	O(m * n)	O(n)
方案一使用了二维数组，更容易理解，但是空间复杂度较高。方案二通过只保留必要的数据，将空间复杂度降低到了 O(n)，但是代码相对复杂一些。在实际应用中，可以根据空间和时间的需求选择合适的方案。