DP #1143 Longest Common Subsequence

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int i = text1.length(), j = text2.length();
        // int[][] dp = new int[i][j];
        // for (int[] r : dp)
        // Arrays.fill(r, -1);
        // return recur(i - 1, j - 1, text1, text2, dp);
        return tabOpt(text1, text2, i, j);
    }

    // Space optimised Tabulation solution
    int tabOpt(String t1, String t2, int n, int m) {
        int[] prev = new int[m + 1];
        int[] cur = new int[m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (t1.charAt(i - 1) == t2.charAt(j - 1))
                    cur[j] = prev[j - 1] + 1;
                else {
                    int tk1 = prev[j];
                    int tk2 = cur[j - 1];
                    cur[j] = Math.max(tk1, tk2);
                }
            }
            prev = (int[]) cur.clone();
        }
        return prev[m];
    }

    // Tabulation solution
    int tab(String t1, String t2, int n, int m) {
        int[][] dp = new int[n][m];
        if (t1.charAt(0) == t2.charAt(0))
            dp[0][0] = 1;
        for (int i = 1; i < n; i++)
            dp[i][0] = (dp[i - 1][0] == 1) ? 1 : ((t1.charAt(i) == t2.charAt(0)) ? 1 : 0);
        for (int i = 1; i < m; i++)
            dp[0][i] = (dp[0][i - 1] == 1) ? 1 : ((t1.charAt(0) == t2.charAt(i)) ? 1 : 0);

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (t1.charAt(i) == t2.charAt(j))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else {
                    int tk1 = dp[i - 1][j];
                    int tk2 = dp[i][j - 1];
                    dp[i][j] = Math.max(tk1, tk2);
                }
            }
        }
        return dp[n - 1][m - 1];
    }

    // Recursive solution
    int recur(int i, int j, String t1, String t2, int[][] dp) {
        if (i < 0 || j < 0)
            return 0;
        if (t1.charAt(i) == t2.charAt(j)) {
            return dp[i][j] = 1 + recur(i - 1, j - 1, t1, t2, dp);
        }
        if (dp[i][j] != -1)
            return dp[i][j];
        int tk1 = recur(i - 1, j, t1, t2, dp);
        int tk2 = recur(i, j - 1, t1, t2, dp);
        return dp[i][j] = Math.max(tk1, tk2);
    }
}