力扣题647回文子串
发布日期:2022-03-04 11:48:21 浏览次数:3 分类:技术文章

本文共 2976 字,大约阅读时间需要 9 分钟。

给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

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

示例 1:

输入:s = "abc"

输出:3
解释:三个回文子串: "a", "b", "c"
示例 2:

输入:s = "aaa"

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

1.自己的解法:把每个子串都拿出来,然后判断这个子串是不是回文子串。用到双重循环,循环时每次定好一个起点,然后不断滑动窗口,判断能不能形成回文子串。

class Solution {    public int countSubstrings(String s) {        int count = 0;        int length = s.length();        for (int i = 0;i < length;i++) {//起点下标            for (int j = 2;j <= length - i;j++) {//从当前起点可以形成的子串的长度,从2开始算是因为长度为1肯定是回文                String str = s.substring(i,i + j);//计算出当前子串                if (isSubstring(str)) {//如果当前子串是回文子串                    count++;//数量加1                }            }        }        count += s.length();//最后加上长度为1的子串的数量        return count;    }    //判断是不是回文子串的方法    public boolean isSubstring(String s) {        int left = 0;//左侧        int right = s.length() - 1;//右侧        while (left <= right) {            if (s.charAt(left) != s.charAt(right)) {                return false;            }            left++;            right--;        }        return true;    }}

   但是这种方法效率低。

2.优化:枚举每一个可能的回文中心(即每个字符),然后用两个指针分别向左右两边扩展,当两个指针指向的元素相同的时候就拓展,否则停止拓展。注意中心可以是两个字符,也可以是一个字符(对应子串的长度为偶数和奇数)

class Solution {    public int countSubstrings(String s) {        int length = s.length();        int count = 0;        for (int i = 0;i < length;i++) {//以每个字符为中心            for (int j = 0;j <= 1;j++) {//中心可能是1个字符,也可能是两个字符                int left = i,right = i + j;                while (left >= 0 && right < length && s.charAt(left) == s.charAt(right)) {                    count++;                    left--;                    right++;                }            }        }        return count;    }}

3.Manacher算法。

        参考:

 

   在这里也可以计算出每个位置的最长子串长度即Len[i],把每个位置能够形成的回文串数量加起来即可。此时每个字符只需要匹配一次。

class Solution {    public int countSubstrings(String s) {        int n = s.length();        //在开头和末尾分别加上"$"和"!"是为了防止越界        StringBuffer t = new StringBuffer("$#");        for (int i = 0; i < n; ++i) {            t.append(s.charAt(i));//在每个字符中间用"#"进行间隔            t.append('#');        }        n = t.length();        t.append('!');        int[] len = new int[n];        int p = 0;//之前的回文子串达到的最右端的下标        int p0 = 0;//最右端下标对应的中心点的下标        int count = 0;//回文串数量        for (int i = 1; i < n; ++i) {//遍历每个字符,因为前面有一个"$",所以从下标1开始            // 初始化 f[i]            // 如果当前遍历到的中心大于了之前保存的最右端,说明没被匹配过,直接赋初值为1            // 如果小于等于之前保存的最右端,说明一部分是已经匹配成功的\            // 接着要判断是否超出了p,超出p的部分需要一个个匹配            len[i] = i <= p ? Math.min(p - i + 1, len[2 * p0 - i]) : 1;            // 中心拓展            while (t.charAt(i + len[i]) == t.charAt(i - len[i])) {                ++len[i];            }            // 动态维护 p0 和 p            if (i + len[i] - 1 > p) {                p0 = i;                p = i + len[i] - 1;            }            // 统计答案, 当前贡献为 (len[i] - 1) / 2 上取整            count += len[i] / 2;        }        return count;    }}

题源:

转载地址:https://blog.csdn.net/xxyneymar/article/details/122336524 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:力扣题617合并二叉树
下一篇:Redis入门(一)

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月06日 03时44分40秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

php linux权限,Linux权限详细介绍 2019-04-21
典型环节的matlab仿真分析,典型环节的MATLAB仿真.doc 2019-04-21
Php contenttype类型,各种类型文件的Content Type 2019-04-21
php使用redis持久化,redis如何持久化 2019-04-21
php7.1解压包安装,【Swoole】php7.1安装swoole扩展 2019-04-21
linux centos删除安装的包,CentOS yum认为已删除的软件包仍在安装中 2019-04-21
酒店管理系统c语言带注释,酒店管理系统--C语言版.pdf 2019-04-21
c语言 实现sizeof功能,C语言简单实现sizeof功能代码 2019-04-21
c语言sin函数近似值,用泰勒公式求sin(x)的近似值 2019-04-21
c 语言登录系统源代码,c语言源代码---------------个人图书管理系统 2019-04-21
android线程通信方式,Android 主线程和子线程通信问题 2019-04-21
cps1 cps2 android,图文教程:CPS1和CPS2模拟器使用 2019-04-21
在线设计 html5 表单,html5注册表单制作-表单制作-小程序表单制作 2019-04-21
android小闹钟课程设计,《小闹钟》教学设计 2019-04-21
mysql文件系统_MySQL文件系统先睹为快(1) 2019-04-21
nums在python_程序找到一对(i,j),其中nums [i] + nums [j] +(i -j)在Python中最大化?... 2019-04-21
jquery后台内容管理_教育平台项目后台管理系统:课程内容模块 2019-04-21
grouping函数 mysql_sql聚合函数有哪些 2019-04-21
python os.walk如何不遍历隐藏文件_python 获取文件下所有文件或目录os.walk()的实例... 2019-04-21
python 股票估值_【中金固收·固收+】隐藏价值的角落:限售股AAP估值及Python实现方法(上)... 2019-04-21