Longest Common Subsequence

| January 11, 2016 | Dynamic Programming | 1 Comment

Longest Common Subsequence implementation in java.

Longest common subsequence (LCS) of 2 sequences is a subsequence, with maximal length, which is common to both the sequences.

Given two sequence of strings, A=[a1,a2,…,an] and B=[b1,b2,…,bm], find any one longest common subsequence.

Dynamic Programming

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
   package com.test.dynamic.programming;
 /*
 * We have two strings X = {"ABCBDAB"}  and Y = {"BDCABA"}
 * Output must be : LCS(X, Y) = {"BCBA", "BDAB", "BCAB"} 
 *
 * Solution :
 * i = X.length() and j = Y.lenght()   
 * LCS(i,j),
 *    if X[i-1] == Y[j-1], then LCS(X[i-1], Y[j-1])
 *    if X[i-1] != Y[j-1], then Max(LCS(X[i-1], Y[j]), LCS(X[i], Y[j-1]))
 *
 *
 */
public class LongestCommonSubsequence {
   
  public static int LCSLength(String X, String Y){
    return LCSLength(X.toCharArray(), X.length(), Y.toCharArray(), Y.length());
  }
   
  /*
   * This is only Recursive Solution, very time consuming O(2^n). Now we need to add memorization
   * technique convert this into Dynamic Programming. And reduce the time complexity to polynomial instead of
   * exponential.
   */
  private static int LCSLength(char[] X, int i, char[] Y, int j) {
     
    if (i==0 || j==0){
      return 0;
    }
    else if (X[i-1] == Y[j-1]){
      return 1 + LCSLength(X, i-1, Y, j-1);
    }else {
      return Math.max(LCSLength(X, i-1, Y, j), LCSLength(X, i, Y, j-1));
    }
  }
   
  /* Dynamic Programming Solution
   * longest common subsequence
   *
   * Using memorization, LCS[][] = new int[m][n]; where m = X.lenth() and n = Y.length()
   * LCS[0][j] = 0, for all j, coz we are not considering X only taking Y
   * LCS[i][0] = 0, for all i, coz we are not considering Y only taking X
   * LCS[i][j] = 1 + LCS(i-1, j-1) if X[i-1] == Y[j-1]
   * LCS[i][j] = max(LCS(i-1,j), LCS(i, j-1)) if X[i-1] != Y[j-1]
   *
   * Bottom Up Construction
   * Time : O(m*n)
   * Space : O(m*n)
   */
  public static int LCSLengthDP(char[] X, char[] Y){
    int m = X.length;
    int n = Y.length;
    int [][] LCS = new int[m+1][n+1];
    int i,j;
    for (i=0; i<=m; i++){
      LCS[i][0] = 0;
    }
     
    for (j=0; j<=n; j++){
      LCS[0][j] = 0;
    }
     
    for (i=1; i<=m; i++){
      for (j=1; j<=n; j++){
        if (X[i-1]==Y[j-1]) {
          LCS[i][j] = 1 + LCS[i-1][j-1];
        }else{
          LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);
        }
      }
    }
    return LCS[m][n];
  }
   
  public static void main(String[] args) {
    String X = "ABCBDAB";
    String Y = "BDCABA";
    System.out.println(LCSLength(X, Y));
    System.out.println(LCSLengthDP(X.toCharArray(), Y.toCharArray()));
  }
   
   
 
 
}

About The Author

Rrohit

Java Developer...Entrepreneur at Heart ...Love Coding...Practice Yoga...ArtOFLiving.

One Comment
  1. RamboCoder Reply

    Great piece of code , can u pls add more dp problems.

Add a Comment

Your email address will not be published. Required fields are marked *