Java函数实现查找两个字符串的最长公共子序列

在Java中实现查找两个字符串的最长公共子序列可以使用动态规划算法来解决。

动态规划是一种常用的求解最优问题的方法，它将问题划分为若干个子问题，并通过求解子问题的最优解来求解原问题的最优解。在本问题中，可以将两个字符串分别为str1和str2，定义一个二维数组dp，其中dp[i][j]表示str1的前i个字符和str2的前j个字符的最长公共子序列的长度。

具体的动态规划过程如下：

1. 初始化dp数组，使其大小为(str1.length+1)×(str2.length+1)，并将dp数组的所有元素初始化为0。

2. 从左到右、从上到下遍历dp数组，根据以下规则更新dp数组的值：

- 如果str1的第i个字符等于str2的第j个字符，则dp[i][j] = dp[i-1][j-1] + 1；

- 否则，dp[i][j] = Max(dp[i-1][j], dp[i][j-1])，即取左边的值和上边的值的较大值。

3. 最后，dp[str1.length][str2.length]即为str1和str2的最长公共子序列的长度。

代码示例如下：

public class LongestCommonSubsequence {
    public static int findLongestCommonSubsequence(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m+1][n+1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                } else if (str1.charAt(i-1) == str2.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];
    }

    public static void main(String[] args) {
        String str1 = "abcde";
        String str2 = "ace";
        int result = findLongestCommonSubsequence(str1, str2);
        System.out.println("The length of the longest common subsequence is: " + result);
    }
}

上述代码中，我们使用两个嵌套循环遍历dp数组，在每个位置更新dp数组的值。最后输出最长公共子序列的长度。

上述代码的时间复杂度为O(m*n)，其中m和n分别为str1和str2的长度。