回文子串

问题陈述

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

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

1
2
3
输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".

动态规划法

状态:dp[i][j] 表示字符串s在[i,j]区间的子串是否是一个回文串。
状态转移方程:当 s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1]) 时,dp[i][j]=true,否则为false。

1、当只有一个字符时,比如a自然是一个回文串。
2、当有两个字符时,如果是相等的,比如aa,也是一个回文串。
3、当有三个及以上字符时,比如ababa这个字符记作串1,把两边的a去掉,也就是bab记作串2,可以看出只要串2是一个回文串,那么左右各多了一个a的串1必定也是回文串。所以当s[i]==s[j]时,自然要看dp[i+1][j-1]是不是一个回文串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution{
public int countSubString(String s){
boolean[][] dp=new boolean[s.length()][s.length()];
int res=0;
for(int j=0;j<s.length();j++){
for(int i=0;i<=j;i++){
if(s.charAt(i)==s.charAt(j)&&(j-i<2||dp[i+1][j-1])){
dp[i][j]=true;
res++;
}
}
}
return res;
}
}

中心扩展法

比如对一个字符串ababa,选择最中间的a作为中心点,往两边扩散,第一次扩散发现left指向的是b,right指向的也是b,所以是回文串,继续扩散,同理ababa也是回文串。

这个是确定了一个中心点后的寻找的路径,然后我们只要寻找到所有的中心点,问题就解决了。

中心点一共有多少个呢?看起来像是和字符串长度相等,但你会发现,如果是这样,上面的例子永远也搜不到abab,想象一下单个字符的哪个中心点扩展可以得到这个子串?似乎不可能。所以中心点不能只有单个字符构成,还要包括两个字符,比如上面这个子串abab,就可以有中心点ba扩展一次得到,所以最终的中心点由2 * len - 1个,分别是len个单字符和len - 1个双字符。

如果上面看不太懂的话,还可以看看下面几个问题:

为什么有 2 * len - 1 个中心点?
aba 有5个中心点,分别是 a、b、a、ab、ba
abba 有7个中心点,分别是 a、b、b、a、ab、bb、ba
什么是中心点?
中心点即left指针和right指针初始化指向的地方,可能是一个也可能是两个
为什么不可能是三个或者更多?
因为3个可以由1个扩展一次得到,4个可以由两个扩展一次得到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution6472 {
public int countSubstrings(String s) {
// 中心扩展法
int ans = 0;
for (int center = 0; center < 2 * s.length() - 1; center++) {
// left和right指针和中心点的关系是?
// 首先是left,有一个很明显的2倍关系的存在,其次是right,可能和left指向同一个(偶数时),也可能往后移动一个(奇数)
// 大致的关系出来了,可以选择带两个特殊例子进去看看是否满足。
int left = center / 2;
int right = left + center % 2;

while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
ans++;
left--;
right++;
}
}
return ans;
}
}