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];
}
}

Exploring and discovering. Learning everyday.