add 1143

fishercoder1534 · fishercoder1534 · commit 2b1186924f32 · 2021-07-08T16:55:33.000-07:00
diff --git a/README.md b/README.md
@@ -344,6 +344,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1152|[Analyze User Website Visit Pattern](https://leetcode.com/problems/analyze-user-website-visit-pattern/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1152.java) |[:tv:](https://youtu.be/V510Lbtrm5s) |Medium|HashTable, Sort, Array|
 |1150|[Check If a Number Is Majority Element in a Sorted Array](https://leetcode.com/problems/check-if-a-number-is-majority-element-in-a-sorted-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1150.java)|[:tv:](https://youtu.be/-t2cdVs9cKk) |Easy||
 |1146|[Snapshot Array](https://leetcode.com/problems/snapshot-array/)|[Javascript](./javascript/_1146.js)| | Easy ||
+|1143|[Longest Common Subsequence](https://leetcode.com/problems/longest-common-subsequence/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1143.java) | |Medium||String, DP
 |1138|[Alphabet Board Path](https://leetcode.com/problems/alphabet-board-path/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1138.java)| [:tv:](https://youtu.be/rk-aB4rEOyU)| Medium |HashTable, String|
 |1137|[N-th Tribonacci Number](https://leetcode.com/problems/n-th-tribonacci-number/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1137.java) | |Easy||
 |1136|[Parallel Courses](https://leetcode.com/problems/parallel-courses/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1136.java) | |Medium||
diff --git a/src/main/java/com/fishercoder/solutions/_1143.java b/src/main/java/com/fishercoder/solutions/_1143.java
@@ -0,0 +1,46 @@
+package com.fishercoder.solutions;
+
+public class _1143 {
+    public static class Solution1 {
+        /**
+         * credit: https://leetcode.com/problems/longest-common-subsequence/solution/
+         * <p>
+         * Recall that there are two different techniques we can use to implement a dynamic programming solution; memoization and tabulation.
+         * <p>
+         * Memoization is where we add caching to a function (that has no side effects). In dynamic programming, it is typically used on recursive functions for a top-down solution that starts with the initial problem and then recursively calls itself to solve smaller problems.
+         * Tabulation uses a table to keep track of subproblem results and works in a bottom-up manner: solving the smallest subproblems before the large ones, in an iterative manner. Often, people use the words "tabulation" and "dynamic programming" interchangeably.
+         * <p>
+         * For most people, it's easiest to start by coming up with a recursive brute-force solution and then adding memoization to it. After that, they then figure out how to convert it into an (often more desired) bottom-up tabulated algorithm.
+         */
+        public int longestCommonSubsequence(String text1, String text2) {
+            if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) {
+                return 0;
+            }
+            int m = text1.length();
+            int n = text2.length();
+            int[][] dp = new int[m + 1][n + 1];
+            for (int i = 0; i < m; i++) {
+                for (int j = 0; j < n; j++) {
+                    dp[i][j] = -1;
+                }
+            }
+            return topDownRecursiveSolve(dp, 0, 0, text1, text2);
+        }
+
+        private int topDownRecursiveSolve(int[][] dp, int i, int j, String text1, String text2) {
+            if (dp[i][j] != -1) {
+                return dp[i][j];
+            }
+            //option1: we don't include text1.charAt(i) in the optimal solution
+            int option1 = topDownRecursiveSolve(dp, i + 1, j, text1, text2);
+            //option2: we do include text1.charAt(i) in the optimal solution as long as a match in text2 at or after j does exist
+            int firstOccurence = text2.indexOf(text1.charAt(i), j);
+            int option2 = 0;
+            if (firstOccurence != -1) {
+                option2 = 1 + topDownRecursiveSolve(dp, i + 1, firstOccurence + 1, text1, text2);
+            }
+            dp[i][j] = Math.max(option1, option2);
+            return dp[i][j];
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1143Test.java b/src/test/java/com/fishercoder/_1143Test.java
@@ -0,0 +1,37 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1143;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1143Test {
+    private static _1143.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1143.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(3, solution1.longestCommonSubsequence("abcde", "ace"));
+    }
+
+    @Test
+    public void test2() {
+        assertEquals(3, solution1.longestCommonSubsequence("abc", "abc"));
+    }
+
+    @Test
+    public void test3() {
+        assertEquals(0, solution1.longestCommonSubsequence("abc", "def"));
+    }
+
+    @Test
+    public void test4() {
+        assertEquals(2, solution1.longestCommonSubsequence("ezupkr", "ubmrapg"));
+    }
+
+}
