题目描述补充

题目：最长重复子序列（Longest Common Subsequence, LCS）

给定两个字符串 text1 和 text2，找出这两个字符串中最长的公共子序列（不一定连续）的长度。一个字符串的子序列是指从一个字符串中删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。

示例：

• 输入：text1 = "abcde", text2 = "ace"
• 输出：3
• 解释：最长公共子序列是 "ace"，所以它的长度为 3。

PHP 示例代码

function longestCommonSubsequence($text1, $text2) {
    $m = strlen($text1);
    $n = strlen($text2);
    
    // 创建一个二维数组来保存子问题的解
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));
    
    // 填充dp表
    for ($i = 1; $i <= $m; $i++) {
        for ($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] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
            }
        }
    }
    
    // 返回最长公共子序列的长度
    return $dp[$m][$n];
}

// 测试代码
echo longestCommonSubsequence("abcde", "ace"); // 输出: 3

Python 示例代码

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    
    # 创建一个二维数组来保存子问题的解
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 填充dp表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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[m][n]

# 测试代码
print(longestCommonSubsequence("abcde", "ace")) # 输出: 3

JavaScript 示例代码

function longestCommonSubsequence(text1, text2) {
    const m = text1.length;
    const n = text2.length;
    
    // 创建一个二维数组来保存子问题的解
    const dp = new Array(m + 1).fill(0).map(() => new 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];
}

// 测试代码
console.log(longestCommonSubsequence("abcde", "ace")); // 输出: 3

码小课网站中有更多关于算法和数据结构的内容分享给大家学习，欢迎大家访问学习更多知识！