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;
}