计算回文子串的个数

Question

我今天在 hackerearth.com 上解决了一个问题。 https://www.hackerearth.com/problem/algorithm/subpalindrome-4/description/

问题：
对于作为输入给出的每个字符串，您需要告诉我们它的回文子序列的数量（不一定是不同的）。注意空串不是回文。
样本输入
1
aab
示例输出
4
解释： "aab"的回文子序列为："a"、"a"、"b"、"aa"，方法returns 4.

我不得不计算回文子串（不明显）的总数。我必须通过两个测试用例，其中一个成功，并且样本输入运行成功。第二个测试用例失败，匹配率为 35.29%。

这是我在 Java 中写的代码，没有使用 StringBuffer class:

import java.util.*;

class TestClass {
    int palin(String a)
    {
        int l=a.length();
        for(int i=0;i<l/2;i++)
        {
            if(a.charAt(i)!=a.charAt(l-1-i))
            return -1;
        }

        return 1;

    }
    public static void main(String args[] ) throws Exception {

        TestClass ob=new TestClass();

        Scanner in=new Scanner(System.in);
        int N = in.nextInt();
        in.nextLine(); /*I have included this because I have seen that when I
        input the string, the number is the value of N appears at its start*/
        for (int ii = 0; ii < N; ii++)
        {
            String aa=in.nextLine();
            String a=aa.toLowerCase();
            int l=a.length();
            int n=l;
            for(int i=0;i<l;i++)
            {
                for(int j=i+2;j<=l;j++)
                {
                    if(ob.palin(a.substring(i,j))>0)
                    n++;
                }
            }
            System.out.println(n);
        }
    }

我是不是逻辑上哪里出错了？还是我错过了什么？

Answer 1

字符串的子序列不同于子字符串。例如，考虑字符串 "ABC":

子字符串："", "A", "B", "C", "AB", "BC", "ABC"

子序列：所有子串，加上 "AC"

关于子序列的更多信息：https://en.wikipedia.org/wiki/Subsequence

计算回文子串的个数

Counting the number of sub-strings that are palindrome

java

algorithm

palindrome