当前位置:   article > 正文

【剑指Offer(专项突破)】020. 回文子字符串的个数(Java实现) 详细解析_java 回文字符串的数量

java 回文字符串的数量

目录

题目: 

         拓展比较:

leetcode题目连接:力扣

分析:

Java代码实现:

注意:

复杂度分析:

代码执行结果:


题目:

给定一个字符串 s ,请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

示例 1:

输入:s = "aaa"
输出:6
解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

拓展比较:

题019. 最多删除一个字符得到回文

题018. 有效的回文

leetcode题目连接:力扣

分析:

解法:中心拓展法

该题可以罗列出所有可能的字符串再分别判断是否是回文字符,但是这样的方式时间复杂度很高,还可以换一种方式:从回文中心判断

依次遍历字符串的字符,将遍历到的每个字符作为回文中心,两个指针都从该回文中心出发向两边遍历,每遇到相同的两个字符则count加1,直到遇到不相等的两个字符,说明不能形成回文了

当然,以上这种情况是基于字符串是奇数的情况:回文中心只有1个,若偶数情况呢?偶数时存在两个回文中心 i 和 i+1,那么两个指针就分别指向 i 和 i+1,

梳理以上思路,可以得出解题步骤:依次遍历字符串,每个遍历到的字符作为奇树回文中心 i 判断有多少个回文,以及作为偶数回文中心 i 和 i+1 判断有多少个回文

Java代码实现:

  1. class Solution {
  2. public int countSubstrings(String s) {
  3. int count = 0;
  4. for(int i = 0; i < s.length(); i++){
  5. count += countPalindrome(s,i,i);
  6. if(i < s.length()-1){
  7. count += countPalindrome(s,i,i+1);
  8. }
  9. }
  10. return count;
  11. }
  12. //判断以该字符最为回文中心有多少个回文字符
  13. public int countPalindrome(String s,int left, int right){
  14. int count = 0;
  15. while(left >= 0 && right <= s.length()-1){
  16. if(s.charAt(left) == s.charAt(right)){
  17. count++;
  18. left --;
  19. right ++;
  20. } else {
  21. break;
  22. }
  23. }
  24. return count;
  25. }
  26. }

复杂度分析:

时间复杂度:O(n^2), 枚举回文中心的是 O(n),对于每个回文中心拓展的次数也是 O(n) 

空间复杂度:O(1)

代码执行结果:

 

以上为个人做题笔记,很多是自己的理解,若有错误还请各位大佬指出~

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/799623
推荐阅读
相关标签
  

闽ICP备14008679号