647. Palindromic Substrings
题目描述
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
LeetCode647. Palindromic Substrings中等
示例 1:
输入: "abc"
输出: 3
解释: 3 个回文子串: "a", "b", "c"。
示例 2:
输入: "aaa"
输出: 6
说明: 6 个回文子串: "a", "a", "a", "aa", "aa", "aaa"。
注意:
输入的字符串长度不会超过 1000。
Java 实现
class Solution {
public int countSubstrings(String s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
count += extractPalindrome(s, i, i);
count += extractPalindrome(s, i, i + 1);
}
return count;
}
public int extractPalindrome(String s, int left, int right) {
int count = 0;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
count++;
left--;
right++;
}
return count;
}
}
相似题目
5. 最长回文子串
516. 最长回文子序列
参考资料
https://leetcode-cn.com/problems/palindromic-substrings/
https://leetcode.com/problems/palindromic-substrings/
