Java算法之最长公共子序列问题(LCS)实例分析

算法简介

最长公共子序列（Longest Common Subsequence，LCS）问题是指：给定两个序列X和Y，找出X和Y的最长公共子序列。

例如，若X=a,b,c,b,d,a,b，Y=b,d,c,a,b,a，则X和Y的最长公共子序列为b,c,a,b，长度为4。

算法思想

LCS问题可以使用动态规划的方法求解，主要思想是：

• 建立一个二维数组dp，dp[i][j]表示X的前i个字符与Y的前j个字符的最长公共子序列的长度。
• 初始状态为dp[0][j]=dp[i][0]=0。
• 当X[i-1]=Y[j-1]时，dp[i][j]=dp[i-1][j-1]+1。
• 当X[i-1]!=Y[j-1]时，dp[i][j]=max(dp[i-1][j],dp[i][j-1])。

算法实现

以下是Java语言实现LCS算法的代码：

public static String lcs(String str1, String str2) {
    int len1 = str1.length();
    int len2 = str2.length();
    int[][] dp = new int[len1+1][len2+1];
    for (int i = 0; i < len1; i++) {
        for (int j = 0; j < len2; j++) {
            if (str1.charAt(i) == str2.charAt(j)) {
                dp[i+1][j+1] = dp[i][j]+1;
            } else {
                dp[i+1][j+1] = Math.max(dp[i+1][j],dp[i][j+1]);
            }
        }
    }
    StringBuilder sb = new StringBuilder();
    while (len1 != 0 && len2 != 0) {
        if (dp[len1][len2] == dp[len1-1][len2]) {
            len1--;
        } else if (dp[len1][len2] == dp[len1][len2-1]) {
            len2--;
        } else {
            sb.append(str1.charAt(len1-1));
            len1--;
            len2--;
        }
    }
    return sb.reverse().toString();
}

算法示例说明1

对于字符串"abcbdab"和"bdcaba"，它们的最长公共子序列为"bdab"，长度为4。

String str1 = "abcbdab";
String str2 = "bdcaba";
String result = lcs(str1, str2);
System.out.println(result); // bdab

算法示例说明2

对于字符串"ABCBDAB"和"BDCABA"，它们的最长公共子序列为"BCBA"，长度为4。

String str1 = "ABCBDAB";
String str2 = "BDCABA";
String result = lcs(str1, str2);
System.out.println(result); // BCBA

以上就是Java算法之最长公共子序列问题(LCS)实例分析的完整攻略了。