package leetcode;

/**
 * https://leetcode.com/problems/longest-common-subsequence/
 */
public class Problem1143 {
    public int longestCommonSubsequence(String text1, String text2) {
        return longestCommonSubsequence(text1, text2, 0, 0);
    }

    private static int longestCommonSubsequence(String text1, String text2, int i, int j) {
        if (i == text1.length()) {
            return 0;
        }
        if (j == text2.length()) {
            return 0;
        }
        int value;
        if (text1.charAt(i) == text2.charAt(j)) {
            value = longestCommonSubsequence(text1, text2, i + 1, j + 1) + 1;
        } else {
            value = longestCommonSubsequence(text1, text2, i + 1, j) +
                longestCommonSubsequence(text1, text2, i, j + 1);
        }
        return value;
    }

    public static void main(String[] args) {
        Problem1143 prob = new Problem1143();
        System.out.println(prob.longestCommonSubsequence("abcde", "ace")); // 3
//        System.out.println(prob.longestCommonSubsequence("ace", "abcde")); // 3
//        System.out.println(prob.longestCommonSubsequence("abc", "abc")); // 3
//        System.out.println(prob.longestCommonSubsequence("abc", "def")); // 0
    }
}

@@ -236,16 +236,61 @@
 t2, 0, 0
+, new Integer%5Btext1.length()%5D%5Btext2.length()%5D
 );%0A    %7D
@@ -379,16 +379,34 @@
 i, int j
+, Integer%5B%5D%5B%5D memo
 ) %7B%0A    
@@ -527,32 +527,107 @@
 rn 0;%0A        %7D%0A
+        if (memo%5Bi%5D%5Bj%5D != null) %7B%0A            return memo%5Bi%5D%5Bj%5D;%0A        %7D%0A
         int valu
@@ -750,16 +750,22 @@
 1, j + 1
+, memo
 ) + 1;%0A 
@@ -792,32 +792,41 @@
         value = 
+Math.max(
 longestCommonSub
@@ -856,19 +856,24 @@
 i + 1, j
-) +
+, memo),
 %0A       
@@ -928,16 +928,23 @@
 i, j + 1
+, memo)
 );%0A     
@@ -960,441 +960,49 @@
     
-return value;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1143 prob = new Problem1143();%0A        System.out.println(prob.longestCommonSubsequence(%22abcde%22, %22ace%22)); // 3%0A//        System.out.println(prob.longestCommonSubsequence(%22ace%22, %22abcde%22)); // 3%0A//        System.out.println(prob.longestCommonSubsequence(%22abc%22, %22abc%22)); // 3%0A//        System.out.println(prob.longestCommonSubsequence(%22abc%22, %22def%22)); // 0
+memo%5Bi%5D%5Bj%5D = value;%0A        return value;
 %0A   

Solve problem 1143