1143_Longest_Common_Subsequence

// https://leetcode.com/problems/longest-common-subsequence/

// BOTTOM UP APPROACH - DYNAMIC PROGRAMMING
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char ch1[] = text1.toCharArray();
        char ch2[] = text2.toCharArray();
        return LCS(ch1,ch2,text1.length(),text2.length());
    }
    public int LCS(char X[],char Y[],int m,int n) {
        int L[][] = new int[m+1][n+1];
        for(int i=0;i<=m;i++){
            for(int j=0;j<=n;j++){
                if(i==0 || j==0)
                    L[i][j] = 0;
                else if(X[i-1] == Y[j-1])
                    L[i][j] = L[i-1][j-1] + 1;
                else
                    L[i][j] = (int)Math.max(L[i-1][j],L[i][j-1]);
            }
        }
        return L[m][n];
    }
}

//      RECURSIVE SOLUTION - OVERLAPPING SUBPROBLEMS
//     public int longestCommonSubsequence(String text1, String text2) {
        // char ch1[] = text1.toCharArray();
        // char ch2[] = text2.toCharArray();
        // return LCS(ch1,ch2,text1.length(),text2.length());
//     }
//     public int LCS(char ch1[],char ch2[],int m,int n){
//         if(m == 0||n == 0)
//             return 0;
//         if(ch1[m-1] == ch2[n-1])
//             return 1 + LCS(ch1,ch2,m-1,n-1);
//         else
//             return (int)Math.max(LCS(ch1,ch2,m,n-1),LCS(ch1,ch2,m-1,n));
//     }
    
// }






// SOLUTIONS

// Method1()- recursive solution(Top- down approach)
	// time complexity - O(2^(m+n))
	// space complexity - O(m+n)
	public static int LCSM1(char[] X, char[] Y, int i, int j) {
		if (i <= 0 || j <= 0)
			return 0;
		if (X[i - 1] == Y[j - 1])
			return 1 + LCSM1(X, Y, i - 1, j - 1);
		else
			return Math.max(LCSM1(X, Y, i, j - 1), LCSM1(X, Y, i - 1, j));

	}

	// Method2()- recursive solution with memoization
	// time complexity - O(m*n)
	// space complexity - O(m*n)
	public static int LCSM2(char[] X, char[] Y, int i, int j, Integer[][] dp) {
		if (i <= 0 || j <= 0)
			return 0;

		if (dp[i][j] != null)
			return dp[i][j];

		if (X[i - 1] == Y[j - 1])
			return 1 + LCSM2(X, Y, i - 1, j - 1, dp);
		else
			return dp[i][j] = Math.max(LCSM2(X, Y, i, j - 1, dp), LCSM2(X, Y, i - 1, j, dp));

	}

	// Method3()- DP solution(Bottom up approach)
	// time complexity - O(m*n)
	// space complexity - O(m*n)
	public static int LCSM3(char[] X, char[] Y, int m, int n) {
		int memo[][] = new int[m + 1][n + 1];

		for (int i = 0; i <= m; i++) {
			for (int j = 0; j <= n; j++) {
				if (i == 0 || j == 0)
					memo[i][j] = 0;
				else if (X[i - 1] == Y[j - 1])
					memo[i][j] = memo[i - 1][j - 1] + 1;
				else
					memo[i][j] = Math.max(memo[i - 1][j], memo[i][j - 1]);
			}
		}
		return memo[m][n];
	}

	// Method4()- DP solution(Bottom up approach)
	// time complexity - O(m*n)
	// space complexity - O(n)
	public static int LCSM4(char[] X, char[] Y, int m, int n) {
		int memo[] = new int[n + 1];

		for (int i = 1; i <= m; i++) {
			int prev = 0;
			for (int j = 1; j <= n; j++) {
				int temp = memo[j];
				if (X[i - 1] == Y[j - 1]) {
					memo[j] = prev + 1;
				} else {
					memo[j] = Math.max(memo[j], memo[j - 1]);
				}
				prev = temp;
			}

		}
		return memo[n];
	}