Java统计回文子串个数,回文子串的个数问题（Java）

题目描述

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

("回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。)

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

输入描述

输入一个字符串S 例如“aabcb”(1 <= |S| <= 50), |S|表示字符串S的长度。

输出描述

符合条件的字符串有"a",“a”,“aa”,“b”,“c”,“b”,“bcb”

分析

对于这道题，首先得想明白，如果采用穷举法，怎样能把所有的解都列举出来。

经常遇到两类问题：一、其中一个最优解；二、所有的最优解。对于其中一个最优解，通常采用贪心算法(你就尽情猜吧，虽然有时它是最优的，你证明不了，但如果能够根据生活认知也可以尝试写写)、分支限界法(广度遍历)来进行求解；而对于所有的解，通常采用回溯法(类似于穷举法，但需要选择合适的穷举规则；深度遍历)。

这道题解题的思考过程：

(1)首先根据生活常识，用最笨的穷举法看看如果得到所有值；

(2)在穷举法的基础上，想想有没有优化的方式(注：既然是算法题，也不太可能让

你用最笨的穷举法来实现)；

(3)因为是求所有的解，但是这个求解是可以拆分的，长度为1的有多少种，长度为2的有多少种，。。。长度为N的有多少种。仔细思考一下，如果把长度小的先计算出来，并把结果记录下来，那么我计算长度较大的结果不就是可以用上之前较小长度的计算结果了吗？

仔细一想，这不就是典型的动态规划法吗，如果稍微了解下动态规划法，程序直接就能写出来了

import java.io.BufferedReader;

import java.io.InputStreamReader;

public class Main {

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

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String s = br.readLine();

if(s == null || s.length() == 0) {

System.out.println(0);

}

char[] sChar = s.toCharArray();

int len = sChar.length;

int i;

int j;

int k;

int[][] arr = new int[len][len];

int sum = 0;

for(i = 0; i < len; i++) {

arr[i][i] = 1;

sum += 1;

}

for(i = 2; i <= len; i++) {

j = 0;

k = j + i - 1;

while(k < len) {

if(sChar[j] == sChar[k]) {

if(j + 1 <= k - 1) {

arr[j][k] = arr[j + 1][k - 1];

sum += arr[j + 1][k -1];

}else {

arr[j][k] = 1;

sum += 1;

}

}

j++;

k++;

}

}

System.out.println(sum);

}

}