LeetCode 1143.

package lc_1143;

public class Solution {
//    public int longestCommonSubsequence(String text1, String text2) {
//        String lon = text1;
//        String shor = text2;
//        if (text2.length() > text1.length()){
//            lon = text2;
//            shor = text1;
//        }
//        return recur(lon.length() - 1, shor.length() - 1, lon, shor);
//    }
//
//    public int recur(int current_l, int current_s, String lon, String shor){
//        if (current_l < 0 || current_s < 0) return 0;
//
//        if (lon.substring(0, current_l + 1).contains(shor.substring(0, current_s + 1))) return current_s + 1;
//
//        int ind_l = -1;
//
//        for (int i=current_l; i>=0; i--){
//            if (shor.charAt(current_s) == lon.charAt(i)){
//                ind_l = i;
//                break;
//            }
//        }
//        if (ind_l >= 0){
//            return Math.max(recur(current_l, current_s-1, lon, shor),
//                    recur(ind_l-1, current_s-1, lon, shor) + 1);
//        }
//        return Math.max(recur(current_l, current_s-1, lon, shor),
//                recur(ind_l, current_s-1, lon, shor));
//    }
    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 (i == 1 && j == 1)
                    if (text1.charAt(0) == text2.charAt(0)) dp[1][1] = 1;

                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                if (text1.charAt(i-1) == text2.charAt(j-1)){
                    dp[i][j] = Math.max(dp[i-1][j-1] + 1, dp[i][j]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}