Longest Common Subsequence (LCS) algorithm using Dynamic Programming in java

Longest Common Subsequence (LCS) algorithm using Dynamic Programming in java

Longest Common Subsequence (LCS) algorithm using Dynamic Programming in java  

The Longest Common Subsequence (LCS) problem is given with two strings like "ABAZDC" and "BACBAD". LCS is to find their longest common subsequence that appear left-to-right but not necessarily in a contiguous block in both the strings. Here we will see how to achieve Longest Common Subsequence (LCS) algorithm using Dynamic Programming using Java.

Example:
Str1 = "ABAZDC"
Str2 = "BACBAD"

Here the Longest Common Subsequence (LCS) size will be 4 and the Longest Common Subsequence (LCS) will "ABAD".

How to find Longest Common Subsequence (LCS)?

First we need to construct matrix of size str1 and str2 like matrix[str1.length][str2.matrix] as shown below

Whenever any character matches with both the array then we need to increment the value by 1 and carry on with same comparison for all rows and columns.
Same comparison will be done using recursion and by storing the value to achieve dynamic programming.  

public class LCS {

 public static void main(String[] args) {

  String str1 = "ABAZDC";
  String str2 = "BACBAD";

  LCS obj = new LCS();
  String out = obj.getLCS(str1, str2);

  System.out.println("LCS Length : " + out.length());
  System.out.println("LCS String : " + out);
 }

 public String getLCS(String str1, String str2) {

  /* Array will be updated with the character change order */
  int arr[][] = new int[str1.length()][str2.length()];
  
  /* Calling actual LCS recursive method */
  getLCS(str1, str1.length() - 1, str2, str2.length() - 1, arr);

  return constructLCSString(arr, str1, str2);
 }
 
 /*
  * Constructing the LCS string the generated array arr[]
  */
 public String constructLCSString(int[][] arr, String str1, String str2) {
  
  String lcsString = "";
  
  /* Iterating through arr[] to get the actual LCS string 
   * iterating from bottom to up.
   */
  for (int i = arr.length - 1, j = arr[0].length - 1; (i >= 0 && j >= 0);) {

   if (i == 0) {
    lcsString = str1.charAt(i) + lcsString;
    break;
   } else if (j == 0) {
    lcsString = str2.charAt(j) + lcsString;
    break;
   }

   if (arr[i][j] != arr[i - 1][j] && arr[i][j] != arr[i][j - 1]) {
    lcsString = str1.charAt(i) + lcsString;
    i--;j--;
   } else if (arr[i][j] == arr[i - 1][j]) {
    i--;
   } else if (arr[i][j] == arr[i][j - 1]) {
    j--;
   }
  }
  return lcsString;
 }
 
 
 public int getLCS(String str1, int n, String str2, int m, int arr[][]) {
  if (n == -1 || m == -1)
   return 0;
  
  /*
   * Checking in array for same n, m index and if present returning 
   * the value from array and its Dynamic programming
   */
  if (arr[n][m] != 0)
   return arr[n][m];

  int output = 0;
  if (str1.charAt(n) == str2.charAt(m)) {
   output = 1 + getLCS(str1, n - 1, str2, m - 1, arr);
  } else {
   int tmp1 = getLCS(str1, n - 1, str2, m, arr);
   int tmp2 = getLCS(str1, n, str2, m - 1, arr);
   output = tmp1 > tmp2 ? tmp1 : tmp2;
  }
  /* Memorize the output on array to use for similar recursive call */
  arr[n][m] = output;
  return output;
 }
}

OUTPUT:

LCS Length : 4
LCS String : ABAD