1143. 最长公共子序列(Medium)

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

样例

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

题解

本题和上一题的 编辑距离(72) 基本上一模一样，但是本题是 Medium。

还是一样，使用两种方法实现：递归+记忆化、动态规划

代码

递归+记忆化

上一题，我们从右向左（n --> 0）走，这里，我们写一个从左向右（0 --> n）走

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

// f(i, j) 返回 s1[:i] 和 s[:j] 的最长公共子序列
func f(i, j int) int {
    if i == l1 || j == l2 {
        return 0
    }

    v, ok := cache[Key{i, j}]
    if ok {
        return v 
    }

    if s1[i] == s2[j] { // 找到一个
        cache[Key{i, j}] = f(i + 1, j + 1) + 1
        return cache[Key{i, j}]
    } else {
        cache[Key{i, j}] = max(f(i + 1, j), f(i, j + 1)) // 因为没有匹配上，继续匹配
       return cache[Key{i, j}]
    }
}

type Key struct {
    i int 
    j int 
}

var s1, s2 string
var l1, l2 int 
var cache map[Key]int // 记忆化操作

func longestCommonSubsequence(text1 string, text2 string) int {
    s1, s2 = text1, text2
    l1, l2 = len(text1), len(text2)
    cache = make(map[Key]int)
    return f(0, 0)
}

动态规划

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

func longestCommonSubsequence(text1 string, text2 string) int {
    n, m := len(text1), len(text2)
    length := make([][]int, n + 1)
    for i := 0; i <= n; i++ {
        length[i] = make([]int, m + 1)
    }

    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if text1[i - 1] == text2[j - 1] {
                length[i][j] = length[i - 1][j - 1] + 1
            } else {
                length[i][j] = max(length[i - 1][j], length[i][j - 1])
            }
        }
    }

    return length[n][m]
}