# 647. 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.

``````class Solution {
public:
int countSubstrings(string s) {
if (s.empty()) return 0;
int n = s.size(), res = 0;
for (int i = 0; i < n; ++i) {
helper(s, i, i, res);
helper(s, i, i + 1, res);
}
return res;
}
void helper(string s, int i, int j, int& res) {
while (i >= 0 && j < s.size() && s[i] == s[j]) {
--i; ++j; ++res;
}
}
};
``````

``````class Solution {
public:
int countSubstrings(string s) {
int n = s.size(), res = 0;
vector<vector<bool>> dp(n, vector<bool>(n));
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j) {
dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1]);
if (dp[i][j]) ++res;
}
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/647

Longest Palindromic Subsequence

Longest Palindromic Substring

https://leetcode.com/problems/palindromic-substrings/

https://leetcode.com/problems/palindromic-substrings/discuss/105689/Java-solution-8-lines-extendPalindrome

https://leetcode.com/problems/palindromic-substrings/discuss/105688/Very-Simple-Java-Solution-with-Detail-Explanation

https://leetcode.com/problems/palindromic-substrings/discuss/105707/Java-DP-solution-based-on-longest-palindromic-substring

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation