字符串的回文子串 java
时间: 2023-08-08 12:14:09 浏览: 62
好的,以下是Java实现字符串的回文子串的代码示例:
```java
public class PalindromicSubstring {
public int countSubstrings(String s) {
int n = s.length();
int count = 0;
boolean[][] dp = new boolean[n][n];
// 枚举回文子串的长度
for (int len = 1; len <= n; len++) {
// 枚举回文子串的起始位置
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (len == 1) { // 单个字符是回文子串
dp[i][j] = true;
} else if (len == 2) { // 两个相同字符是回文子串
dp[i][j] = (s.charAt(i) == s.charAt(j));
} else { // 多个字符时,判断首尾字符是否相同,以及中间部分是否为回文子串
dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i+1][j-1];
}
if (dp[i][j]) {
count++;
}
}
}
return count;
}
}
```
这里使用动态规划的思想,时间复杂度为 $O(n^2)$,空间复杂度也是 $O(n^2)$。具体做法是:定义 $dp[i][j]$ 表示字符串从 $i$ 到 $j$ 是否是回文子串,然后根据回文子串的定义进行状态转移。最后统计回文子串的数量即可。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)