双指针
时间复杂度O(n^2) 空间复杂度O(1)
class Solution {
public:
int countSubstrings(string s) {
int res = 0;
for(int i = 0; i < s.size(); i++) {
res += nums(s, i, i, s.size());//以i为中心寻回文串数
res += nums(s, i, i+1, s.size());//以i、i+1为中心寻回文串数
}
return res;
}
int nums(const string &s, int i, int j, int n) {
int res = 0;
//双指针双向遍历判定回文串
while(i >= 0 && j < n && s[i] == s[j]) {//if(……) WA
i--;
j++;
res++;
}
return res;
}
};
DP
时间复杂度 O(n^2) 空间复杂度 O(n^2)
class Solution {
public:
int countSubstrings(string s) {
//dp[i][j]表示s[i]~s[j]是否是回文串
vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), 0));
int res = 0;
//dp[i][j]由dp[i+1][j-1]推来,故i由大到小遍历
for(int i = s.size(); i >= 0; i--) {
for(int j = i; j < s.size(); j++) {
if(s[i] == s[j]) {
if(j - i <= 1 || dp[i+1][j-1]) {
dp[i][j] = 1;
res++;
}
}
}
}
return res;
}
};