647 回文子串

本文最后更新于：2021年4月12日 晚上

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

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

示例 1：

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

示例 2：

1
2
3
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

  • 输入的字符串长度不会超过 1000 。

Solution

参考：[5 最长回文子串]、[ 516 最长回文子序列 ]

  • 动态规划 和 中心扩散法
  • 方法与 [5 最长回文子串] 完全相同，后者求长度。

状态转移方程：

1
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

说明：

「动态规划」事实上是在填一张二维表格，由于构成子串，因此 i 和 j 的关系是 i <= j ，因此，只需要填这张表格对角线以上的部分。

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
// @lc code=start
class Solution {
public:
    int countSubstrings(string s) {
        if (s.size() <= 0) return 0;
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int res = 0;
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i <= j; ++i) {
                if (s[i] == s[j]) {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                } else {
                    dp[i][j] = false;
                }
                if (dp[i][j] == true) res++;
            }
        }
        return res;
    }
};
// @lc code=end
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！