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;
}
Last updated
Was this helpful?