判断一个字符串是否是一个回文除了从两端向里移动指针,也可以采用指针从字符串中心开始向两端延伸。即如果存在一个长度为m的回文子字符串,再分别向该回文两端延伸一个字符,并判断这两个字符是否相同,如果相同则找到了一个长度为m+2的子字符串。
另外,回文的长度即可以是奇数也可以是偶数,所以回文的中心即可能是一个字符,也可能是两个字符。
首先遍历字符串中的每个字符,以每个字符为中心,调用方法统计以当前字符为中心的回文子串数量(回文长度为奇数情况),以及以当前字符和下一个字符为中心的回文子串数量(回文长度为偶数情况),并将结果累加到总计数中。最终返回总计数。
方法通过两个指针从中心向两侧扩展,判断对应位置的字符是否相等,如果相等则回文子串数量加一,直到不再满足回文条件。
public int countSubstrings(String s) {
// 处理边界情况:空字符串或长度为0的字符串
if (s == null || s.isEmpty()) {
return 0;
}
int count = 0; // 统计回文子串的总数量
// 遍历字符串中的每个字符
for (int i = 0; i < s.length(); i++) {
// 以当前字符为中心,统计回文子串数量
count += countPalindrome(s, i, i);
// 以当前字符和下一个字符为中心,统计回文子串数量
count += countPalindrome(s, i, i + 1);
}
return count;
}
// 统计以给定起始位置 start 和结束位置 end 为中心的回文子串数量
public int countPalindrome(String s, int start, int end) {
int count = 0; // 统计回文子串的数量
// 通过两个指针从中心向两侧扩展,判断对应位置的字符是否相等
while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
count++; // 如果相等,回文子串数量加一
start--; // 移动左指针
end++; // 移动右指针
}
return count;
}