leetcode 回文子串 中等

leetcode 回文子串 中等

 

 

①:马拉车的 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 }

 

leetcode 回文子串 中等

上一篇:C# 委托实例(跨窗体操作控件)


下一篇:django--提交数据并展示