最长公共子序列(Longest Common Subsequence,LCS)是字符串处理中的经典问题。给定两个字符串,找出它们的最长公共子序列,即在不改变字符顺序的情况下,从这两个字符串中抽取的最长的子序列。本文将详细介绍最长公共子序列的原理、实现及其应用。
最长公共子序列问题可以通过动态规划(Dynamic Programming)来解决。其基本思想是构建一个二维数组 dp
,其中 dp[i][j]
表示字符串 text1
的前 i
个字符和字符串 text2
的前 j
个字符的最长公共子序列的长度。
text1[i-1] == text2[j-1]
,则 dp[i][j] = dp[i-1][j-1] + 1
。text1[i-1] != text2[j-1]
,则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
。i == 0
或 j == 0
时,dp[i][j] = 0
,因为空字符串与任何字符串的公共子序列长度为0。以下是最长公共子序列的JavaScript实现:
/**
* 动态规划实现最长公共子序列
* @param {string} text1 - 第一个字符串
* @param {string} text2 - 第二个字符串
* @return {number} - 最长公共子序列的长度
*/
function longestCommonSubsequence(text1, text2) {
const m = text1.length;
const n = text2.length;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); // 初始化 dp 数组
for (let i = 1; i <= m; i++) {
for (let 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] = Math.max(dp[i - 1][j], dp[i][j - 1]); // 状态转移方程
}
}
}
return dp[m][n]; // 返回最长公共子序列的长度
}
// 示例
const text1 = "abcde";
const text2 = "ace";
console.log(longestCommonSubsequence(text1, text2)); // 输出: 3
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
:创建一个二维数组,大小为 (m+1) x (n+1)
,并初始化为0。for (let i = 1; i <= m; i++)
:遍历字符串 text1
的每个字符。for (let j = 1; j <= n; j++)
:遍历字符串 text2
的每个字符。if (text1[i - 1] === text2[j - 1])
:如果当前字符相同,则 dp[i][j] = dp[i - 1][j - 1] + 1
。else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
:如果当前字符不同,则 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
。return dp[m][n];
:返回 dp
数组的最后一个元素,即最长公共子序列的长度。最长公共子序列是字符串处理中的经典问题,通过动态规划的方法,可以高效地解决这个问题。理解和掌握最长公共子序列的算法,可以应用于文本比较、版本控制、基因序列分析和数据比较等领域。