Dynamic Programming : An example showing Lowest Common Subsequence in Java

Introduction

Optimal Substructure : A problem is said to be a optimal substructure if an optimal solution can be constructed from optimal solution of it’s subproblem.

Overlapping subproblems : A problem is said to have overlapping subproblems if the problem can be broken down into repetitive subproblems.

Greedy Algorithm is used to solve problems having optimal substructure. But if the same problem has overlapping subproblems, dynamic programming is used in such cases.

The Problem

Longest Common Subsequence : Let’s say, we have two strings  ABXC and ADYC.

Here, the longest common subsequence(lcs) is AC. But how? If you see the strings backward, you will realise that both have ‘C’ at the end. That effectively means that our longest common subsequence has ‘C’ at the end and now the problem has reduced to find the longest common subsequence of ABX and ADY.

ABX and ADY don’t have anything common at the end, so what should will be the lcs here. Either it will lcs of AB and ADY or it will be lcs of ABX and AD; depending upon which one is greater.

LCS of AB and ADY in turn depends on A and ADY or AB and AD. Similarly we could go on recursively to see following pair of substrings evaluated for lcs between them

Recursive pairs are : ABXC-ADYC
Recursive pairs are : ABX-ADY
Recursive pairs are : AB-ADY
Recursive pairs are : A-ADY
Recursive pairs are : -ADY
Recursive pairs are : A-AD
Recursive pairs are : -AD
Recursive pairs are : A-A
Recursive pairs are : –
Recursive pairs are : AB-AD
Recursive pairs are : A-AD
Recursive pairs are : AB-A
Recursive pairs are : A-A
Recursive pairs are : AB-
Recursive pairs are : ABX-AD
Recursive pairs are : AB-AD
Recursive pairs are : ABX-A
Recursive pairs are : AB-A
Recursive pairs are : ABX-

You will notice that this problem can be solved recursively. Here’s the code for that:

import java.util.Arrays;
import java.util.Date;
import java.util.HashMap;
import java.util.Map;
public class LongestCommonSubsequence {
public static void main(String args[]) {
long timestamp1 = System.currentTimeMillis();
System.out.println("—————Longest Common Subsequence Using Recursive Method—————–");
String string1 = "AGGTABNDSV";
String string2 = "GXTXAYBDFGHOI";
String longestCommonSubsequence = findLongestSubsequence(string1, string2);
System.out.println("LCS is "+new StringBuilder(longestCommonSubsequence).reverse().toString());
long timestamp2 = System.currentTimeMillis();
System.out.println(" Time Taken : "+(timestamp2timestamp1));
}
private static String findLongestSubsequence(String string1, String string2) {
char[] charArray1 = string1.toCharArray();
char[] charArray2 = string2.toCharArray();
int arraylength1 = string1.length() 1;
int arraylength2 = string2.length() 1;
String longestCommonSubsequence = "";
if (arraylength1 < 0 || arraylength2 < 0)
return longestCommonSubsequence;
String newStr1 = String.valueOf(Arrays.copyOfRange(charArray1, 0, arraylength1));
String newStr2 = String.valueOf(Arrays.copyOfRange(charArray2, 0, arraylength2));
if (charArray1[arraylength1] == charArray2[arraylength2]) {
longestCommonSubsequence = longestCommonSubsequence + charArray1[arraylength1];
longestCommonSubsequence = longestCommonSubsequence + findLongestSubsequence(newStr1, newStr2);
} else {
String res1 = findLongestSubsequence(newStr1, String.valueOf(charArray2));
String res2 = findLongestSubsequence(String.valueOf(charArray1), newStr2);
if (res1.length() > res2.length()) {
longestCommonSubsequence = longestCommonSubsequence + res1;
} else
longestCommonSubsequence = longestCommonSubsequence + res2;
}
return longestCommonSubsequence;
}
}

The output for this code is:

—————Longest Common Subsequence Using Recursive Method—————–
LCS is GTABD
Time Taken : 192 ms

However, if you notice the recursive pairs that I mentioned above, there are many pairs in duplicate whose computation we can avoid with little space. We can store the recursive pair and lcs for that in a hashmap and check that before going for the recursive approach. Here’s the code for that:

https://gist.github.com/anonymous/15b65cf2edf846b5f8a96e9b5fb77286

The output for this code is :

—————Longest Common Subsequence Using Recursive Method And Memoization—————–
LCS is GTABD
Time Taken : 1 ms

Did you notice the difference in time taken in both case? Memoization increased the speed by 190 times.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Create a free website or blog at WordPress.com.

Up ↑

%d bloggers like this: