回文子字符串的数目

问题：给你一个字符串，请输出该字符串里有多少个回文子字符串。如果两个子字符串的起始位置或者结束位置不同，那么即使它们的内容一样也是不同的子字符串。

例如，字符串"abc"有3个回文子字符串，分别为"a"、"b"和"c"；"aaa"有6个回文子字符串，分别为"a"、"a"、"a"、"aa"、"aa"和"aaa"。

分析：

这是LeetCode的第647题。

解法一：动态规划

我们分析以字符串中第i个字符结尾的子字符串中回文的数目。首先，任意一个字符本身都是一个长度为1的回文子字符串。

其次，如果第i个字符和它前面的第i-1个字符相同。那么，它们组成一个长度为2的回文子字符串。例如：字符串"abba"中，两个相邻的"b"组成一个长度为2的回文"bb"。

另外，如果以第i-1个字符为结尾的子字符串中有一个长度为m的回文子字符串，并且第i个字符和该回文前面一个字符（下标为i-m-1）相同，那么以第i个字符结尾的子字符串中有一个长度为m+2的回文。例如字符串"abba"中，下标为3的字符"a"（下标从0开始计数）前面有一个长度为2的回文"bb"，由于"bb"的前面的字符也是"a"，因此它们共同组成一个长度为4的回文"abba"。

基于这个思路，我们可以写出如下的Java代码：

在上述代码中，链表prevLengths是以第i-1个字符为结尾的所有回文子字符串的长度。由于需要这么一个链表，因此该解法的空间复杂度是O(n)。另外，由于该解法需要两个嵌套的循环，因此时间复杂度是O(n^2)。

解法二：从回文的特点入手

如果我们找到一个长度为m的回文子字符串，我们分别向该回文的两端延伸一个字符，并判断回文前后的字符是否相同。如果相同，我们就找到了一个长度为m+2的回文。例如，在字符串"abcba"中，我们从中间的"c"出发向两端延伸一个字符，由于"c"前后都是"b"，因此我们找到了一个长度为3的回文"bcb"。接着我们再向两端延伸一个字符，由于"bcb"的前后都是"a"，所以我们有找到一个长度为5 的回文"abcba"。

值得注意的是，回文的长度可以是奇数，也可以是偶数。长度为奇数的回文，其对称中心只有一个字符；而长度为偶数的回文，其对称中心有两个字符。

基于这个思路，我们可以写出如下代码：

上述解法仍然需要两个嵌套的循环，因此时间复杂度还是O(n^2)。但该解法只用到了若干变量，其空间复杂度是O(1)。