力扣题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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.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
jquery后台内容管理_教育平台项目后台管理系统:课程内容模块
2019-04-21
grouping函数 mysql_sql聚合函数有哪些
2019-04-21