最长公共子序列
七崽爱吃小饼干2026/02/09阅读 0
最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
codeType
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
codeType
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
codeType
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
提示：
- 1 <= text1.length, text2.length <= 1000
- text1 和 text2 仅由小写英文字符组成。
解法
ts
function longestCommonSubsequence(text1: string, text2: string): number {
// dp[i][j]表示text1以第i个字符为结尾的序列
// 和text2以第j个字符为结尾的子序列的最长公共子序列长度
// 如果text1[i] === text2[j]
// dp[i][j] = dp[i - 1][j - 1] + 1
// 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
const n = text1.length
const m = text2.length
const dp = new Array(n).fill(0).map(() => new Array(m).fill(0))
let max = -Infinity
for(let i = 0; i < n; i++){
for(let j = 0; j < m; j++){
if(i === 0 && j === 0){
dp[i][j] = text1[i] === text2[j] ? 1 : 0
max = Math.max(max, dp[i][j])
continue
}
if(text1[i] === text2[j]){
dp[i][j] = (i === 0 || j === 0) ? 1 : dp[i - 1][j - 1] + 1
}else{
dp[i][j] = Math.max(i === 0 ? 0 : dp[i - 1][j], j === 0 ? 0 : dp[i][j - 1])
}
max = Math.max(max, dp[i][j])
}
}
return max
};