回文子串
难度:
标签:
题目描述
代码结果
运行时间: 34 ms, 内存: 16.2 MB
/*
* 思路:
* 使用Java Stream进行回文子串的计算,
* 通过IntStream生成索引并使用lambda表达式处理。
*/
import java.util.stream.IntStream;
public class SolutionStream {
public long countSubstrings(String s) {
return IntStream.range(0, s.length())
.mapToLong(i -> IntStream.range(i, s.length())
.filter(j -> isPalindrome(s, i, j))
.count())
.sum();
}
private boolean isPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
}
解释
方法:
这个题解的思路是先找出字符串中所有连续相同字符构成的子串,统计它们的回文子串数量。接着再枚举连续子串的两端,向两边拓展,统计由不同字符构成的回文子串数量。最后将两部分的数量相加得到答案。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在处理连续相同字符的子串时,可以直接使用公式 (1 + (j-i+1)) * (j-i+1) / 2 来计算回文子串的数量?
▷🦆
在向两边扩展检查回文子串时,为什么只需要检查一次每对字符即可断定是否为回文?是否有可能遗漏某些情况?
▷🦆
在枚举连续相同字符子串的两端并向两边扩展时,如果两边扩展遇到相同的字符会如何处理?
▷🦆
为什么连续相同字符的子串处理完后,还需要单独处理向两边扩展的情况?
▷相关问题
最长回文子串
给你一个字符串 s
,找到 s
中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
示例 1:
输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd" 输出:"bb"
提示:
1 <= s.length <= 1000
s
仅由数字和英文字母组成