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