Merge pull request IIdroyII#34 from vedic-kalra/main

IIdroyII · web-flow · commit 00a441ae2c55 · 2021-10-15T01:26:36.000+05:30
Longest Common Subsequence CPP Implementation
diff --git a/longest_common_subsequence_using_dp.cpp b/longest_common_subsequence_using_dp.cpp
@@ -0,0 +1,73 @@
+//here i am providing two solutions to the following problems using dynamic programming
+//one is Top-Down DP and another is Bottom-Up DP
+// this paticular questions corresponds to the folloing question on leetcode
+//leetcode-1143 https://leetcode.com/problems/longest-common-subsequence/
+//here i have explained the question in a gradual optimal manner
+//------------------------------------------------------------------------------------------------------------------
+//brute force approach
+class Solution {
+    public int longestCommonSubsequence(String text1, String text2) {
+        return longestCommonSubsequence(text1, text2, 0, 0);
+    }
+    
+    private int longestCommonSubsequence(String text1, String text2, int i, int j) {
+        if (i == text1.length() || j == text2.length())
+            return 0;
+        if (text1.charAt(i) == text2.charAt(j))
+            return 1 + longestCommonSubsequence(text1, text2, i + 1, j + 1);
+        else
+            return Math.max(
+                longestCommonSubsequence(text1, text2, i + 1, j),
+                longestCommonSubsequence(text1, text2, i, j + 1)
+            );
+    }
+}
+//------------------------------------------------------------------------------------------------------------------
+/* Top-down DP
+We might use memoization to overcome overlapping subproblems.
+Since there are two changing values, i.e. i and j in the recursive 
+function longestCommonSubsequence, we might apply a two-dimensional array.*/
+class Solution {
+    private Integer[][] dp;
+    public int longestCommonSubsequence(String text1, String text2) {
+        dp = new Integer[text1.length()][text2.length()];
+        return longestCommonSubsequence(text1, text2, 0, 0);
+    }
+    
+    private int longestCommonSubsequence(String text1, String text2, int i, int j) {
+        if (i == text1.length() || j == text2.length())
+            return 0;
+        
+        if (dp[i][j] != null)
+            return dp[i][j];
+            
+        if (text1.charAt(i) == text2.charAt(j))
+            return dp[i][j] = 1 + longestCommonSubsequence(text1, text2, i + 1, j + 1);
+        else
+            return dp[i][j] = Math.max(
+                longestCommonSubsequence(text1, text2, i + 1, j),
+                longestCommonSubsequence(text1, text2, i, j + 1)
+            );
+    }
+}
+//------------------------------------------------------------------------------------------------------------------
+/*Bottom-up DP
+For every i in text1, j in text2, we will choose one of the following two options:
+
+if two characters match, length of the common subsequence would be 1 plus the 
+length of the common subsequence till the i-1 andj-1 indexes
+if two characters doesn't match, we will take the longer by either skipping i or j indexes*/
+class Solution {
+    public int longestCommonSubsequence(String text1, String text2) {
+        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
+        for (int i = 1; i <= text1.length(); i++) {
+            for (int j = 1; j <= text2.length(); j++) {
+                if (text1.charAt(i - 1) == text2.charAt(j - 1))
+                    dp[i][j] = 1 + dp[i - 1][j - 1];
+                else
+                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
+            }
+        }
+        return dp[text1.length()][text2.length()];
+    }
+}
