## 计算字符串中回文子串的个数 Palindromic Substrings 原

叶枫啦啦

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

```Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".```

Example 2:

```Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".```

Note:

1. The input string length won't exceed 1000.

①  计算字符串中回文子串的个数，使用动态规划解决：

d[i][j]表示从i到j的字符串为是否回文，真则为（1），否则为假（0），

class Solution { //22ms
public int countSubstrings(String s) {
int len = s.length();
int res = 0;
boolean[][] dp = new boolean[len][len];
for (int i = len - 1;i >= 0;i --){
for (int j = i;j < len;j ++){
dp[i][j] = ((s.charAt(i) == s.charAt(j) && ((j - i < 3) || dp[i + 1][j - 1])));
if (dp[i][j]){
res ++;
}
}
}
return res;
}
}

② 从中间向两边递归判断回文字符串。

class Solution { //12ms
public int countSubstrings(String s) {
if (s == null || s.length() == 0) return 0;
int len = s.length();
int res = 0;
for (int i = 0;i < len;i ++){
res += dfs(s,i,i);
res += dfs(s,i,i + 1);
}
return res;
}
public int dfs(String s,int left,int right){
int res = 0;
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
left --;
right ++;
res ++;
}
return res;
}
}

### 评论(0)

【DP、双指针】647. Palindromic Substrings

2019/06/06
0
0
647. Palindromic Substrings

PilgrimHui
2018/10/08
0
0
LeetCode 647. Palindromic Substrings (回文子字符串)

dby_freedom
2018/12/19
0
0
【Leetcode】647. Palindromic Substrings

Description Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as diffe......

xiagnming
2018/07/30
0
0
【DP、双指针】5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Example 2: 解题思路： 找一个字符串的最长回文子串，......

2019/06/07
0
0

0228 我的潘多拉

18
0
OSChina 周六乱弹 —— 屁会不会传染病毒

Osc乱弹歌单（2020）请戳（这里） 【今日歌曲】 @薛定谔的兄弟 ：分享洛神有语创建的歌单「我喜欢的音乐」: 《ハレハレヤ（朗朗晴天）》- 猫瑾 手机党少年们想听歌，请使劲儿戳（这里） @空格...

63
1

27
0

1.大项目工程且多人维护的弊端 （1）项目团队协同成本高，业务响应越来越慢 （2）应用复杂度已超出人的认知负载（向杂乱的电线一样） （3）错误难于隔离（一个模块出错，整个系统挂掉） （4...

zxx901221

68
0
eclipse 上传jar到远程仓库

63
0