Count number of palindromic subsequences Top down

Правка en1, от aakarshmadhavan, 2018-07-14 23:57:31

Hello, The problem is just

Count the number of palindromic subsequences in a string (they can be duplicates),
Input : str = "aab"
Output : 4
Explanation :- palindromic subsequence are :"a", "a", "b", "aa" 

Please help me come up with recursive solution.

public int sol(String s, int l, int r){
        if(r < l) return 0;
        if(l == r) return 1;
        
        int ans = 0;
        if(s.charAt(l) == s.charAt(r)){
            ans = 1 + sol(s, l + 1, r) + sol(s, l, r - 1) - sol(s, l + 1, r - 1);
        } else {
            ans = sol(s, l + 1, r) + sol(s, l, r - 1) - sol(s, l + 1, r - 1);
        }
        
        return ans;
    }

For test case s = "aaaa" this has failed (it is outputting 10 when the answer is actually 15)

Where am I going wrong? Thanks!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский aakarshmadhavan 2018-07-14 23:57:31 885 Initial revision (published)