Q25 Longest Common Subsequence - LeetCode 1143

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length() , n = text2.length();
        return solve(text1 , text2 , m-1 , n-1 , new Integer[m][n]);
        
        //tabulization-> m*n

        //right shifting of idexes to solve base case in tabulization 
        int dp[][] = new int[m+1][n+1];

        for(int i = 1 ;i < m+1 ; i++){
            for(int j = 1 ; j < n+1 ; j++){

                char ch1 = text1.charAt(i-1) , ch2 = text2.charAt(j-1);

                if(ch1 == ch2)
                dp[i][j] = dp[i-1][j-1] + 1;

                else
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
            
        return dp[m][n];
    }

    //Recursion(2^(m*n)) Memo(m*n) | sc m*n + m*n
    public int solve(String text1 , String text2 , int i , int j, Integer[][]dp ){
        if(i < 0 || j < 0)
        return 0;
        
        if(dp[i][j] != null)
        return dp[i][j];
        
        char ch1 = text1.charAt(i) , ch2 = text2.charAt(j);
        if(ch1 == ch2)
        return dp[i][j] = 1+ solve(text1 , text2 , i-1 , j-1 , dp);

        else{
            int fact = Math.max(solve(text1,text2 ,i-1,j,dp) , solve(text1,text2 ,i,j-1,dp));
            return dp[i][j] = 0 +fact;
        }

    }
}