最长公共子序列

1. 题目描述

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

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

2. 思路

1. 思路一
   • 递归
   • 从最后一个字符开始匹配，相同+1一起往前做，不同则取max（第一个往前，第二个往前）
2. 思路二
   • 动态规划

3. 实现

3.1. DFS

//时间：O(2的N次方)
func longestCommonSubsequence(text1 string, text2 string) int {
	if text1 == "" || text2 == "" {
		return 0
	}

	if text1[len(text1)-1] == text2[len(text2)-1] {
		return 1 + longestCommonSubsequence(text1[:len(text1)-1], text2[:len(text2)-1])
	}

	return max(longestCommonSubsequence(text1[:len(text1)-1], text2),
		longestCommonSubsequence(text1, text2[:len(text2)-1]))
}

func max(data ...int) int {
	max := data[0]
	for i := 1; i < len(data); i++ {
		if data[i] > max {
			max = data[i]
		}
	}
	return max
}

3.2. DFS+记忆化

func longestCommonSubsequence(text1 string, text2 string) int {
    memo := make(map[string]int, 0)
    return longestCommonSubsequenceDFS(text1, text2, 0, 0, memo)
}

func longestCommonSubsequenceDFS(text1, text2 string, index1, index2 int, memo map[string]int) int {
    if index1 >= len(text1) || index2 >= len(text2) {return 0}
    key := buildKey(index1, index2)
    count, ok := memo[key]
    if ok {
        return count
    }
    if text1[index1] == text2[index2] {
        count = 1 + longestCommonSubsequenceDFS(text1, text2, index1+1, index2+1, memo)
    } else {
        count = max(longestCommonSubsequenceDFS(text1, text2, index1+1, index2, memo),
            longestCommonSubsequenceDFS(text1, text2, index1, index2+1, memo))
    }
    memo[key] = count
    return count
}

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

func buildKey(index1, index2 int) string {
    return fmt.Sprintf("%v_%v", index1, index2)
}

3.3. 动态规划

func max(data ...int) int {
	max := data[0]
	for i := 1; i < len(data); i++ {
		if data[i] > max {
			max = data[i]
		}
	}
	return max
}

//时间：O(m*n)
func longestCommonSubsequence2(text1 string, text2 string) int {
	dp := make([][]int, len(text1)+1, len(text1)+1)
	for i := 0; i <= len(text1); i++ {
		dp[i] = make([]int, len(text2)+1, len(text2)+1)
	}

	for i := 1; i <= len(text1); i++ {
		for j := 1; j <= len(text2); 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[len(text1)][len(text2)]
}

4. 参考

• 1143. 最长公共子序列 - 力扣（LeetCode）