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

题目链接

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

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

• $1<=s.length<=1000$
• s由小写英文字母组成

分析：

使用 动态规划 解决本题。

我们定义 $f(i,j)$为 s[i - 1,j - 1]区间是否为回文串。

• 当 $s[i-1]\ne s[j-1]$，那么 f[i][j] = false.
• 当 $s[i-1]=s[j-1]$，
• • 如果 $j-i\le 1$，s[i][j] = true（相当于指针 i和 j指向了一个字符'a'，或者指向了两个相连且相等的字符 'aa'）。
• • 如果 f[i-1][j+1] = true，s[i][j] = true。

时间复杂度： $O(n^2)$

C++代码：

class Solution {
public:int countSubstrings(string s) {int n = s.size();bool f[n+1][n+1];memset(f,false,sizeof f);int ans = 0;for(int i = n;i >= 1;i--){for(int j = i;j <= n;j++){if((s[i-1] == s[j - 1]) && (j - i <= 1 || f[i+1][j-1])){ans++;f[i][j] = true;}}}return ans;}
};

Java代码：

class Solution {public int countSubstrings(String s) {int n = s.length();boolean[][] f = new boolean[n+1][n+1];int ans = 0;for(int i = n;i >= 1;i--){for(int j = i;j <= n;j++){if((s.charAt(i-1) == s.charAt(j-1)) && (j - i <= 1 || f[i+1][j-1])){ans++;f[i][j] = true;}}}return ans;}
}