The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in bioinformatics. It is also widely used by revision control systems such as Git for reconciling multiple changes made to a revision-controlled collection of files.
Recursive Solution :
package dp;
public class LCS {
public static int max(int a, int b) {
return a>b?a:b;
}
public static int LCSUtil(String str1, int i, int len1,
String str2, int j, int len2) {
if(i == len1 || j == len2)
return 0;
if(str1.charAt(i)==str2.charAt(j))
return 1 + LCSUtil(str1, i+1, len1, str2, j+1, len2);
return max(LCSUtil(str1, i+1, len1, str2, j, len2),
LCSUtil(str1, i, len1, str2, j+1, len2));
}
public static int FindLCS(String str1, String str2) {
return LCSUtil(str1,0,str1.length(),str2,0,str2.length());
}
public static void main(String[] args) {
String str1 = "ABCBDAB";
String str2 = "BDCABA";
long startTime = System.nanoTime();
System.out.println(FindLCS(str1,str2));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
}
output:
4
Total Time (nanoseconds) : 894489
This is a correct solution but it is very time-consuming. The time complexity of the above solution is O(2^n).
Now We will solve this question using Dynamic Programming by using Memoization:
package dp;
public class LCS {
public static int max(int a, int b) {
return a>b?a:b;
}
public static int LCSUtil(String str1, int i, int len1,
String str2, int j, int len2) {
int[][] dp = new int[len1+1][len2+1];
for(int x=0;x<len1;x++)
dp[x][len2]=0;
for(int x=0;x<len2;x++)
dp[len1][x]=0;
for(int x=len1-1;x>=0;x--) {
for(int y=len2-1;y>=0;y--) {
dp[x][y]=dp[x+1][y+1];
if(str1.charAt(x)==str2.charAt(y)) {
dp[x][y]++;
}
if(dp[x+1][y]>dp[x][y])
dp[x][y]=dp[x+1][y];
if(dp[x][y+1]>dp[x][y])
dp[x][y]=dp[x][y+1];
}
}
return dp[0][0];
}
public static int FindLCS(String str1, String str2) {
return LCSUtil(str1,0,str1.length(),str2,0,str2.length());
}
public static void main(String[] args) {
String str1 = "ABCBDAB";
String str2 = "BDCABA";
long startTime = System.nanoTime();
System.out.println(FindLCS(str1,str2));
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println("Total Time (nanoseconds) : " + (totalTime));
}
}
output:
4
Total Time (nanoseconds) : 275257
The time complexity of the above solution is O(mn). Where m and n are the length of two strings to be compared.
