Java最长公共子序列示例源码

Java最长公共子序列示例源码可以用于找到两个字符串之间的最长公共子序列。以下是Java最长公共子序列示例源码的完整攻略:

1. 题目描述

给定两个字符串s1和s2，找到它们的最长公共子序列（LCS）。

2. 示例

示例1：

输入：s1 = "abcde", s2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度是3。

示例2：

输入：s1 = "abc", s2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度是3。

3. 解法分析

在这个问题中，我们可以使用动态规划的方法来解决。

如果我们定义一个二维数组dp[i][j]来表示s1和s2中前i个和前j个字符的LCS长度，那么我们可以考虑以下几种情况：

1. 如果s1[i-1]和s2[j-1]相同，那么它们肯定在LCS中。此时，dp[i][j] = dp[i-1][j-1] + 1。
2. 如果s1[i-1]和s2[j-1]不同，则它们可能不在LCS中，此时我们需要选择跳过s1[i-1]或者s2[j-1]，哪种选择能让LCS最长，就选哪种。因此，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

最终，dp[s1.length()][s2.length()]表示的就是s1和s2的LCS长度。

4. 代码实现

public int longestCommonSubsequence(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i - 1) == s2.charAt(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];
}

5. 示例说明

示例1

输入的两个字符串是 "abcde" 和 "ace"。我们使用二维数组dp来表示它们之间的LCS长度。

初始化的时候，dp[0][0]表示空字符串的LCS长度为0，那么 dp[0][j] 和 dp[i][0] 也必须都为0，因此 dp 数组的第一行和第一列都初始化为0。

  a   c   e
a 0   0   0
b 0   0   0
c 0   1   1
d 0   1   1
e 0   1   2

我们可以看到，当s1[i-1]和s2[j-1]相同时，dp[i][j] = dp[i-1][j-1] + 1；当s1[i-1]和s2[j-1]不同时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

因此在初始化后的dp数组中，例如dp[3][1]，s1[2]和s2[0]不同，则它们可能不在LCS中，此时我们需要选择跳过s1[2]或者s2[0]，哪种选择能让LCS最长，就选哪种。: dp[3][1] = max(dp[2][1], dp[3][0]) = max(1, 0) = 1。

最终dp[s1.length()][s2.length()]的值就是3，即s1和s2的LCS长度。

示例2

输入的两个字符串是 "abc" 和 "abc"。

初始化的时候，dp[0][0]表示空字符串的LCS长度为0，那么 dp[0][j] 和 dp[i][0] 也必须都为0，因此 dp 数组的第一行和第一列都初始化为0。

  a   b   c
a 0   0   0
b 0   1   1
c 0   1   2

同样的，我们可以看到，当s1[i-1]和s2[j-1]相同时，dp[i][j] = dp[i-1][j-1] + 1；当s1[i-1]和s2[j-1]不同时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

因此最终dp[s1.length()][s2.length()]的值就是3，即s1和s2的LCS长度。