AlgoPressAppearance
0647-回文子串
https://leetcode.cn/problems/palindromic-substrings
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
- 1 <= s.length <= 1000
- s 由小写英文字母组成
思路：回溯法
不能使用回溯，因为子字符串是需要连续的，回溯中会去掉中间某些字符串 暴力两重循环应该会超时
思路：动态规划
dp[i,j] 表示从 i 到 j 组成字符串是否构成回文子串 从后往前遍历数组，因为 dp[i,j] 依赖 dp[i+1,j-1] 的状态 不停计算判断 i,j 组成的字符是否是回文串。 当 s[i] != s[j] 的时候，不是回文串， 当 s[i] == s[j] 的时候，如果他们就是1个或者2个字符，那么是回文串，否则就是 dp[i,j] = dp[i+1,j-1]; 最后每次循环判断是否是回文串，是的话加1
参考代码
csharp
public class Solution {
public int CountSubstrings(string s) {
int n = s.Length;
//动态规划 dp[i,j] 表示从i到j的字符是否可以组成回文数
bool[,] dp = new bool[n,n];
//初始化
int max = 0;
for(int i=0; i<n; i++){
dp[i,i] = true;
max++;
}
//状态转移
for(int i=n-1; i>=0; i--){
for(int j=i+1; j<n; j++){
if(s[i] == s[j]){
dp[i,j] = j-i==1 || dp[i+1,j-1];
}
else{
dp[i,j] = false;
}
if(dp[i,j]){
max++;
}
}
}
return max;
}
}
参考代码：优化
合并1位和2位的回文计算方法
csharp
public class Solution {
public int CountSubstrings(string s) {
int n = s.Length;
//动态规划 dp[i,j] 表示从i到j的字符是否可以组成回文数
bool[,] dp = new bool[n,n];
//初始化
int max = 0;
//状态转移
for(int i=n-1; i>=0; i--){
for(int j=i; j<n; j++){
if(s[i] == s[j]){
dp[i,j] = j-i<=1 || dp[i+1,j-1];
}
else{
dp[i,j] = false;
}
if(dp[i,j]){
max++;
}
}
}
return max;
}
}
Manacher 算法
csharp
public class Solution {
public int CountSubstrings(string s) {
int n = s.Length;
StringBuilder sb = new StringBuilder();
sb.Append("$#");
for(int i=0; i<n; i++){
sb.Append(s[i]);
sb.Append("#");
}
n = sb.Length;
sb.Append("!");
int[] f = new int[n];
int iMax = 0, rMax = 0, ans = 0;
for(int i=1; i<n; i++){
//初始化 f[i]
f[i] = i <= rMax ? Math.Min(rMax - i + 1, f[2*iMax-i]) : 1;
//中心扩展
while(sb[i+f[i]] == sb[i-f[i]]){
f[i]++;
}
//动态维护 iMax 和 rMax
if(i + f[i] -1 > rMax){
iMax = i;
rMax = i + f[i] - 1;
}
//统计答案,当前贡献为 (f[i] -1) / 2 上取整
ans += f[i] / 2;
}
return ans;
}
}
复习动规：注意 dp 表示是否能成回文，然后统计
csharp
public class Solution {
public int CountSubstrings(string s) {
int n = s.Length;
bool[,] dp = new bool[n,n]; //dp[i,j] 表示前i个字符和前j个字符是否能组成回文
int count = 0;
//初始化
for(int i=n-1; i>=0; i--){
for(int j=i;j<n;j++){
if(i == j){ //只有一位
dp[i,j] = true;
}
else if(s[i] == s[j]){ //只有两位
if(i+1 == j){
dp[i,j] = true;
}
else{ //多位
dp[i,j] = dp[i+1,j-1];
}
}
if(dp[i,j]){
count++;
}
}
}
return count;
}
}