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

题目链接：剑指 Offer II 020. 回文子字符串的个数

方法一：动态规划

解题思路

• 状态表示：\(dp[i][j]\) 表示子字符串 \(s[i,j]\) 是否为回文串；
• 状态计算：
  • 若 \(s[i]\) != \(s[j]\)，显然不是；
  • 若 \(s[i]\) == \(s[j]\)，有以下几种可能：
    • \(i\) == \(j\)，只有一个字符，是回文串；
    • \(i\) + \(1\) == \(j\)，有两个字符且两个字符相同，是回文串；
    • \(i\) + \(1\) < \(j\)，此时 \(s[i,j]\) 是否为回文串取决于 \(dp[i + 1][j - 1]\)。
  • 由于当前状态 \(dp[i][j]\) 的计算可能需要 \(dp[i + 1][j - 1]\)，因此 \(i\) 从大到小遍历，\(j\) 从小到大遍历。

代码

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length();
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = 0; i < n; i ++ ) dp[i][i] = true;
        int ans = n; // 一位字符一定为回文串
        for (int i = n - 1; i >= 0; i -- ) {
            for (int j = i + 1; j < n; j ++ ) {
                if (s[i] != s[j]) continue;
                if (j == i + 1 || dp[i + 1][j - 1]) {
                    ans ++ ;
                    dp[i][j] = true;
                }
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(n^2)\)；
空间复杂度：\(O(n^2)\)。

方法二：中心拓展 + 找规律简化

解题思路

官方解答

代码

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size(), ans = 0;
        for (int i = 0; i < 2 * n - 1; ++i) {
            int l = i / 2, r = i / 2 + i % 2;
            while (l >= 0 && r < n && s[l] == s[r]) {
                --l;
                ++r;
                ++ans;
            }
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(n^2)\)；
空间复杂度：\(O(1)\)。