河北建设厅八大员报名网站谷歌google官方网站
题目链接
剑指 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<=10001 <= s.length <= 10001<=s.length<=1000
s由小写英文字母组成
分析：
使用 动态规划 解决本题。
我们定义 f(i,j)f(i,j)f(i,j)为 s[i - 1,j - 1]区间是否为回文串。
- 当 s[i−1]≠s[j−1]s[i-1] \neq s[j-1]s[i−1]=s[j−1]，那么
f[i][j] = false. - 当 s[i−1]=s[j−1]s[i-1] = s[j-1]s[i−1]=s[j−1]，
-
- 如果 j−i≤1j - i \leq1j−i≤1，
s[i][j] = true（相当于指针i和j指向了一个字符'a'，或者指向了两个相连且相等的字符'aa'）。
- 如果 j−i≤1j - i \leq1j−i≤1，
-
- 如果
f[i-1][j+1] = true，s[i][j] = true。
- 如果
时间复杂度： O(n2)O(n^2)O(n2)
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;}
}