①:马拉车的 p 数组,即改造后的字符串,以 i 为中心的最大回文串的长度 p[i],ret += (p[i] / 2);
②:dp[i][j] 表示 i 到 j 是否为回文,dp[i][j] = dp[i + 1][j - 1] & (s[i] == s[j]),为 true 则 ++ret;
class Solution { public: int countSubstrings(const string &s) { string t = "#"; for(int i = 0; i < s.size(); ++ i) { t.push_back(s[i]); t.push_back(‘#‘); } vector<int> p(t.size(), 0); // p[i] 表示以 i 为中心的回文串的最大长度 int mid = -1, mx = -1; // mx 表示当前回文串能涉及的最右边界 + 1, mid 为其对应的中点 int ret = 0; for(int i = 0; i < t.size(); ++ i) { p[i] = mx > i ? min(mx - i, p[2 * mid - i]) : 1; while(i + p[i] < t.size() && i - p[i] >= 0 && t[i + p[i]] == t[i - p[i]]) ++ p[i]; if(i + p[i] > mx) { mid = i; mx = i + p[i]; } ret += p[i] / 2; } return ret; } };
// dp 是 golang 写的, 勉强看一看
const ( ONE_E3 = 1e3 + 10 ONE_E5 = 1e5 + 10 ) func countSubstrings(s string) int { var dp [ONE_E3][ONE_E3]bool var ans int // 枚举长度,有 line 18,需要以长度为单位进行枚举, for dis := 0; dis < len(s); dis ++ { for i := 0; i < len(s) - dis; i ++ { j := i + dis if dis == 0 { dp[i][j] = true } else if dis == 1 { dp[i][j] = s[i] == s[j] } else { dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j] } if dp[i][j] { ans ++ } } } return ans }