647. 回文子串

题目

方法一：动态规划 (自己写的)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution {
public:
    int countSubstrings(string s) {
        // 初始化
        if (s.length() < 2) {
            return 1;
        }
        int n = s.length();
        int res = 0;
        vector<vector<bool>> f(n, vector<bool>(n, false));
        for (int i = 0; i < n; i ++) {
            res ++;
            f[i][i] = true;
            if (i < n - 1 && s[i] == s[i + 1]) {
                f[i][i + 1] = true;
                res ++;
            }
        }

        for (int len = 3; len <= n; len ++) {
            for (int i = 0; i + len <= n; i ++) {
                if (f[i + 1][i + len - 2] && s[i] == s[i + len - 1]) {
                    f[i][i + len  - 1] = true;
                    res ++;
                }
            }
        }

        return res;
    }
};

时间复杂度：O(N^2)，其中 N 是字符串 s 的长度。需要填充一个 N x N 的二维数组。

空间复杂度：O(N^2)，需要使用一个 N x N 的二维数组来存储子问题的解。

方法二：动态规划 (官方题解)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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)，其中 N 是字符串 s 的长度。最坏情况下，所有字符都相同，需要检查所有可能的回文子串。

空间复杂度：O(1)，只使用了常数级别的额外空间。