剑指 Offer II 020. 回文子字符串的个数

剑指 Offer II 020. 回文子字符串的个数

给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

回文串没怎么做过，看到这个题是有点懵的，最后看题解，挨个把方法写了一遍
第一个就是暴力O(n*n*n)的算法

class Solution {
public:

/*方法一：暴力时间复杂度是O(n*n*n)*/
    int countSubstrings(string s) {
        if (s.size() == 0)
            return 0;
        int count = 0;
        
        for (int i = 0; i < s.size(); i++)
        {
            for (int j = i; j < s.size(); j++) {
                if (Pan(i, j, s))
                    count++;
            }
        }
        return count;
    }
    bool Pan(int i,int j, string &s) {
        while (i < j) {
            if (s[i] != s[j])
                break;
            i++;
            j--;
        }
        return i>=j;
    }
}

第二个用了一个dp数组，时间复杂度O(n*n),空间复杂度O(n*n)

/*方法二：dp，时间复杂度是O(n*n)，空间复杂度O(n*n)*/
    int countSubstrings(string s) {
        int n = s.size();
        vectorint>> dp(n, vector<int>(n));
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        int count = n;
        for (int i = n-1; i >=0; i--) {
            for (int j = i+1; j < n; j++) {
                if (s[i] == s[j]) {
                    if (i+1==j) {
                        dp[i][j] = 1;
                        count++;
                    }
                    else {
                        if (dp[i+1][j-1]) {
                            count++;
                            dp[i][j] = 1;
                        }
                    }
                }
            }
        }
        return count;
    }

第三个方法是中心扩散，这个是最常用的一个方法，效率也比较高时间复杂度O(n*n)，空间复杂度O(1)

/*方法三：中心扩散*/
    int n;
    int countSubstrings(string s)
    {
        this->n = s.size();

        int res = 0;
        for (int i = 0; i < n; i++)
        {
            int odd = get_max_len(s, i, i);
            int even = get_max_len(s, i, i + 1);
            res += odd;
            res += even;
        }
        return res;
    }

    int get_max_len(string & s, int l, int r)
    {
        int cnt = 0;
        while (0 <= l && r < n && s[l] == s[r])
        {
            cnt++;
            l--;
            r++;
        }
        return cnt;
    }

第四个方法马拉车，这个算法最高效，时间O(n)，空间O(1)，但是比较难理解，查了很多资料，最后才理解了思想，旦角以后可能也不会去用

    /*方法四：马拉车算法*/
    int countSubstrings(string s)
    {
        //---------------------------- 马拉车算法 ---------------------------//
        string t = "#";
        for (char c : s)
        {
            t += c;
            t += '#';
        }

        int tn = t.size();

        int res = 0;

        vector<int> arm_len;
        int center = -1;
        int maxR = -1;
        for (int i = 0; i < tn; i++)
        {
            int cur_arm_len = 0;
            if (i <= maxR)
            {
                int mirror_i = 2 * center - i;
                int cur_min_len = min(arm_len[mirror_i], maxR - i);
                cur_arm_len = center_spread_get_max_len(t, i - cur_min_len, i + cur_min_len);
            }
            else
            {
                cur_arm_len = center_spread_get_max_len(t, i, i);
            }

            arm_len.push_back(cur_arm_len);

            if (i + cur_arm_len > maxR)
            {
                maxR = i + cur_arm_len;
                center = i;
            }

            res += (cur_arm_len + 1) / 2;       //本题需要的部分
        }

        return res;
    }

    int center_spread_get_max_len(string & t, int l, int r)
    {
        int tn = t.size();
        while (0 <= l && r < tn && t[l] == t[r])
        {
            l--;
            r++;
        }
        return (r - l - 2) / 2;
    }