实现最长公共子序列使用的算法

实现最长公共子序列（LCS）有多种算法，其中比较常用的有动态规划算法和贪心算法。

动态规划算法：

设两个字符串为A和B，LCS为C。定义一个二维数组dp，其中dp[i][j]表示A的前i个字符与B的前j个字符的LCS长度。则：

1. 当i=0或j=0时，dp[i][j]=0；

2. 当A[i-1]=B[j-1]时，dp[i][j]=dp[i-1][j-1]+1；

3. 当A[i-1]!=B[j-1]时，dp[i][j]=max(dp[i][j-1], dp[i-1][j])。

最终C的长度即为dp[A.length][B.length]。

Java代码实现：

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

贪心算法：

该算法的核心思想是：如果两个字符相同，则将其添加到LCS中；如果不同，则舍弃其中一个字符，寻找下一个字符是否与另一个字符串中当前位置的字符相同，直到找到相同字符或遍历完两个字符串。

Java代码实现：

public static String lcs(String A, String B) {
    StringBuilder sb = new StringBuilder();
    int i = 0, j = 0;
    while (i < A.length() && j < B.length()) {
        if (A.charAt(i) == B.charAt(j)) {
            sb.append(A.charAt(i));
            i++;
            j++;
        } else if (A.charAt(i + 1) == B.charAt(j)) {
            i++;
        } else if (A.charAt(i) == B.charAt(j + 1)) {
            j++;
        } else {
            i++;
            j++;
        }
    }
    return sb.toString();
}