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 : "+(timestamp2–timestamp1)); | |
| } | |
| 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:
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.
If you liked this article and would like one such blog to land in your inbox every week, consider subscribing to our newsletter: https://skillcaptain.substack.com
Leave a Reply