leetcode647. 回文子串
暴力
class Solution {
public:
int res=0;
int countSubstrings(string s) {
int n=s.size();
for(int i=0;i<n;i++)
{
//odd
int l=i,r=i;
while(l>=0&&r<n&&s[l]==s[r]) l--,r++,res++;
//even
l=i,r=i+1;
while(l>=0&&r<n&&s[l]==s[r]) l--,r++,res++;
}
return res;
}
};
dp
class Solution {
public:
int res=0;
int countSubstrings(string s) {
int n=s.size();
vector<vector<bool>> f(n+1,vector<bool>(n+1,false));
for(int len=1;len<=n;len++)
for(int i=0;i+len-1<n;i++)
{
int j=i+len-1;
if(1==len) f[i][j]=true;
else if((2==len||f[i+1][j-1])&&s[i]==s[j])
f[i][j]=true;
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(f[i][j]) res++;
return res;
}
};
有帮助的话可以点个赞，我会很开心的~