1143. Longest Common Subsequence

Given two strings text1 and text2, return *the length of their longest common subsequence. *If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

• For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

思路：

题目让求两个字符串的最大公共子序列长度，用动态规划来做，遍历两个字符串，状态转移方程：当A字符串的i位和B字符串的j位相同时候：取前一位的最优解+1 也就是A[i] = B[j] 的时候，dp[i][j] = dp[i][j] + 1。
当不相同的时候，那么只需要把A字符串0~i的最优解或者B字符串0～j的最优解继承下来就行，就是dp[i][j] = max(dp[i][j-1], dp[i-1][j])。
需要注意的是这里的边界情况，可以把存状态的数组都比两个字符串大一点，就能保证走到字符串长度的时候不越界。

代码：

golang:

func longestCommonSubsequence(text1 string, text2 string) int {
    var size1 = len(text1)
    var size2 = len(text2)
    
    var dp = make([][]int, size1 + 1)
    for i := range dp {
        dp[i] = make([]int, size2 + 1)
    }

    // 初始条件都是0
    var maxSize = 0
    
    for i := 0; i < size1; i++ {
        for j := 0; j < size2; j++ {
            // 因为定义的时候都保证比字符串大一位，这里直接够存就行。
            if text1[i] == text2[j] {
                dp[i+1][j+1] = dp[i][j] + 1
            } else {
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
            }
            
            // 更新最大值
            maxSize = max(dp[i+1][j+1], maxSize)
        }
    }
    
    return maxSize
}

func max(i, j int) int {
    if i < j {
        return j
    }
    return i
}