04-最长公共子序列算法

实现一个最长公共子序列算法，并分析其时间复杂度和空间复杂度。

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

最长公共子序列（Longest Common Subsequence，LCS）是一种经典的字符串匹配问题，其目的是找到两个字符串中最长的公共子序列。公共子序列指的是两个字符串中都存在的、顺序一致的字符序列，不一定连续。

LCS算法的实现可以采用动态规划的思想，具体步骤如下：
1.定义状态：设字符串A和B的长度分别为m和n，令dp[i][j]表示A[0:i]和B[0:j]的LCS长度，则最终答案为dp[m][n]。
2.状态转移：当A[i] = B[j]时，dp[i][j] = dp[i-1][j-1] + 1；否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
3.初始化：dp[0][j] = 0和dp[i][0] = 0，其中0 <= i <= m，0 <= j <= n。
4.返回结果：dp[m][n]即为A和B的LCS长度。

时间复杂度分析：该算法的时间复杂度为O(mn)，其中m和n分别为两个字符串的长度。这是因为需要填充一个大小为(m+1)×(n+1)的二维数组，每个格子需要常数时间进行状态转移。

空间复杂度分析：该算法的空间复杂度为O(mn)，同样是因为需要填充一个大小为(m+1)×(n+1)的二维数组。如果需要优化空间复杂度，可以使用滚动数组或者只保留上一行的状态值进行状态转移。

验证：

public static void main(String[] args) {
    String a = "hello";
    String b = "lloabc";
    int lcs = LongestString.longestCommonSubsequence(a, b);
    //lcs = 3
    System.out.println("lcs = " + lcs);
}