NoobCoder's blog

By NoobCoder, history, 5 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it