Longest Common Subsequence

Longest Common Subsequence

Example For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

For "ABCD" and "EACB", the LCS is "AC", return 2.

• State: f[i][j]表示在前i個跟前j個最大的LCS長度

• Func: f[i][j] = if A[i-1]==B[j-1] (f[i-1][j-1]+1) else max{f[i-1][j], f[i][j-1]}

• Init: f[i][0]=f[0][j]=0

• Ans: f[n+1][m+1]

public int longestCommonSubsequence(String A, String B) {
    int lenA = A.length()+1;
    int lenB = B.length()+1;

    int[][] f = new int[lenA][lenB];

    for(int i=1; i<lenA; i++){
        for(int j=1; j<lenB; j++){
            if(A.charAt(i-1) == B.charAt(j-1)){
               f[i][j] = f[i-1][j-1]+1;
           }else{
               f[i][j] = Math.max(f[i-1][j], f[i][j-1]);
           }
        }
    }
    return f[A.length()][B.length()];
}

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    lenA, lenB = len(text1), len(text2)
    dp = [[0] * (lenB+1) for _ in range(lenA+1)]
    
    for i in range(1, lenA+1):
        for j in range(1, lenB+1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                
    return dp[-1][-1]
    
# O(n) space    
def longestCommonSubsequence(self, A, B):
        n, m = len(A), len(B)
        f = [[0] * (m + 1), [0] * (m + 1)]
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if A[i - 1] == B[j - 1]:
                    f[i % 2][j] = f[(i - 1) % 2][j - 1] + 1
                else:
                    f[i % 2][j] = max(f[i % 2][j - 1], f[(i - 1) % 2][j])
        return f[n % 2][m]

Longest Common Substring

• State: f[i][j]表示在i個跟前j個包含i,j最大的LCSubString長度

• Func: f[i][j] = if A[i-1]==B[j-1] (f[i-1][j-1]+1) else 0

• Init: f[i][0]=f[0][j]=0

• Ans: loop to find max

public int longestCommonSubstring(String A, String B) {
    int lenA = A.length();
    int lenB = B.length();

    int[][] f = new int[lenA+1][lenB+1];
    for(int i=1; i<=lenA; i++){
        for(int j=1; j<=lenB; j++){
            if(A.charAt(i-1) == B.charAt(j-1)){
                f[i][j] = f[i-1][j-1]+1;
            }else{
                f[i][j]=0;
            }
        }
    }

    int max=0;
    for(int i=1; i<=lenA; i++){
        for(int j=1; j<=lenB; j++){
            max = Math.max(max, f[i][j]);
        }
    }
    return max;
}