Can Anyone Help me in Formulating Memoized Solution from this Recurrence Solution

Revision en1, by NoobCoder, 2020-04-18 08:41:33

Problem Link :Here

Now This question states find longest palindromic subsequence of S containing the character C.

So Normal Solution without any constraint of Char c is to iterate over String in forward and reverse direction with i-starting from 0 j- starting from length-1

and do normal thing to include or skip

Now in this question i also used boolean flag to check whether character c has been appeared or not till now

public static int solvePalindroimic(int i,int j, boolean isTrue){ if(i>j){// 0,0,false //1 5 false return 0; }

if(i==j){
       if(isTrue==true ||(isTrue==false &&word[i]==x)){
           return 1;
       }
       else{
           return 0;
       }
    }
    boolean res = word[i]==x?true:isTrue;//0 , 0 ,false res  =false//1 ,1 res  =false
    int ans = 0;

    if(word[i]==word[j]){


        ans= solvePalindroimic(i+1,j-1,res);//solve(1,5,false)
        if(ans==0){
            return 0;
        }
        else{
            return ans+2;
        }

    }
          ans  =Math.max(solvePalindroimic(i,j-1,res),solvePalindroimic(i+1,j,word[j]==x?true:isTrue));
    if(ans==0){
        return 0;
    }
    else{
        return ans;
    }


}

if it detect character at any index it return ans or 0 and if it detects return value to be zero than it means no character C is found

this recurrence is working could anyone tell memoized solution please how to formulate it

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English NoobCoder 2020-04-18 08:42:10 18
en1 English NoobCoder 2020-04-18 08:41:33 1849 Initial revision (published)