最长公共子序列 LCS

发表于 阅读次数：

基本概念

最长公共子序列和最长公共子串不同

TQV4F2Z`K_I__3`EL_0P__3.png

递归原理

_F_8_ME22LLWT_II8_C79DH.png

递归公式

假设我们用c[i,j]表示Xi 和 Yj 的LCS的长度（直接保存最长公共子序列的中间结果不现实，需要先借助LCS的长度）。其中X = {x1 … xm}，Y ={y1…yn}，Xi = {x1 … xi}，Yj={y1… yj}。可得递归公式如下：
6NCATV8_558UEHX__J16_NJ.png

案例推导

I27G9X_RSB1AHM7ALT_SBDG.png

最长公共子序列 LCS解法

其中最长的公共子序列长度为dp[n][m]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length(); 
        int m = text2.length();
        int[][] dp = new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            char c1 = text1.charAt(i-1);
            for(int j=1;j<=m;j++){
                char c2 = text2.charAt(j-1);
                if(c1==c2){
                    dp[i][j] = dp[i-1][j-1]+1; 
                }else{
                    dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[n][m];
    }
}