Longest Common Subsequence

Approach 1 : Recursion without memoization

public int longestCommonSubsequence(String text1, String text2) {
        return longestCommonSubsequenceRecursion(0,0,text1,text2);
    }
    
    private int longestCommonSubsequenceRecursion(int index1,int index2, String text1, String text2){
        
        if(index1>=text1.length() || index2>=text2.length()){
            return 0;
        }
        
        if(text1.charAt(index1)==text2.charAt(index2)){
            return longestCommonSubsequenceRecursion(index1+1,index2+1,text1,text2) +1;
        }else{
            
            int temp = longestCommonSubsequenceRecursion(index1+1,index2,text1,text2);
            int max = Math.max(temp, longestCommonSubsequenceRecursion(index1,index2+1,text1,text2));
            
            return max>temp?max:temp;
        }
    }

Approach 2: Dynamic Programming: Recursion with Memoization

public int longestCommonSubsequence(String text1, String text2) {
        int[][] memo = new int[text1.length()][text2.length()];
        return longestCommonSubsequenceMemoizationRecursion(0,0,memo,text1,text2);
    }
    
    private int longestCommonSubsequenceMemoizationRecursion(int index1,int index2, int[][] memo,String text1, String text2){
        
        if(index1>=text1.length() || index2>=text2.length()){
            return 0;
        }
        if(memo[index1][index2]!=0){
            return memo[index1][index2];
        }
        
        if(text1.charAt(index1)==text2.charAt(index2)){
            
            int max= longestCommonSubsequenceMemoizationRecursion(index1+1,index2+1,memo,text1,text2) +1;
            memo[index1][index2] = max;
            return max;
            
        }else{
            
            int temp = longestCommonSubsequenceMemoizationRecursion(index1+1,index2,memo,text1,text2);
            int max = Math.max(temp, longestCommonSubsequenceMemoizationRecursion(index1,index2+1,memo,text1,text2));
            
            max= max>temp?max:temp;
            
            memo[index1][index2] = max;
            
            return max;
        }
    }

Approach 2: Dynamic Programming : Bottom up 2d array

public int longestCommonSubsequence(String text1, String text2) {
        return longestCommonSubSequenceBottomUpDp(text1,text2);
    }
    
    private int longestCommonSubSequenceBottomUpDp(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++){
                
                char rc = text1.charAt(i-1);
                char cc = text2.charAt(j-1);
                
                if(rc==cc){
                    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[text1.length()][text2.length()];
    }

LONGEST COMMON PALINDROMIC SUBSEQUENCE

class Solution {
    public int longestPalindromeSubseq(String s) {
        
        String text1 = s;
        String text2 = new StringBuilder(s).reverse().toString();
        
        int length = s.length();
        
        int[][] dp = new int[length+1][length+1];
for(int i =1;i<=length ; i++){
            
            for(int j =1;j<=length;j++){
                
                char rc = text1.charAt(i-1);
                char cc = text2.charAt(j-1);
                
                if(rc==cc){
                    
                    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[length][length];
    }
}