力扣刷题笔记-05 最长回文子串

这篇具有很好参考价值的文章主要介绍了力扣刷题笔记-05 最长回文子串。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

05 最长回文子串

半山腰有点拥挤,你要去山顶看看。

中心扩展法

什么是回文

从左边出发,字符的顺序和从右边出发是一样的,比如aba,abba。那么基于这个理论,我们就可以想到解决方案:

找一个中心点,向两边出发,左右两边各移动一位,如果相同就证明是回文子串,不相同就停止,找下一个中心点

中心点

我们遍历字符串里面所有的字符,认为每个字符都可以作为中心点。但是要区分两种情况:奇数和偶数

奇数情况下,当前字符就是中心点,往左右两边延伸就行了。比如aba,我们找b就行

偶数情况下,我们找两个字符的两边,比如abba,我们以bb为中心,向两边扩展。在代码上的表述就是,我们来计算这样的数据,然后比较最大值。

// 以任意一个字符为中心,回文串有可能是奇数,也有可能是偶数
 // 比如aba,以b为中心,
 // 比如abba,要以bb中间的缝隙为中心才能找到正确的回文串
 // 所以不管是哪种,我们就都计算下,用max函数去最大的
 int len1 = expendAroundCenter(s,i,i);
 // 偶数回文串,为什么+1就是偶数
 // 因为偶数回文串的中心是两个字符,所以要从i和i+1开始扩展
 int len2 = expendAroundCenter(s,i,i+1);

核心思想:

以每个字符串中的每个字符为中心,向两边扩展,寻找回文子串的长度。我们需要考虑两种情况:

回文串的长度是奇数和偶数文章来源地址https://www.toymoban.com/news/detail-711910.html

  1. 定义两个变量start,end用来记录最长回文子串的起始和结束位置,初始时候都为0;
  2. 在内层循环里有两个指针,left和right,奇数情况下从left和right都是从i开始,偶数情况下left从i开始,right从i+1开始。
  3. 接下来遍历字符串中的每个字符,将其视为可能的回文串的中心。
  4. 判断的方法是从中心出发,向两边扩展,在扩展的过程中我们比较当前左右两边的字符是不是相同,如果相同,就继续向外扩展;如果不相同,就停止扩展。
  5. 一旦我们找到以当前中心为基础的回文子串的长度,就比较它与已知回文子串的长度。
  6. 循环的边界点:外层循环是把字符串读取结束,内层循环是做左指针指向0,右指针指向length-1,同时还要满足左右指针指向的字符是相同的。

code

class Solution {
    public String longestPalindrome(String s) {
        // 判断字符串是不是为空
        if (s.length() == 0 || s == null) {
            return "";
        }

        // 定义最长回文子串的起始位置
        int start = 0;
        int end = 0;
        // 以每个字符为中心,向两边扩展,对比左右两边是不是相等,如果相等,就继续扩展。
        // 左右两边相等说明是回文串
        for (int i = 0;i<s.length();i++){

            // 以任意一个字符为中心,回文串有可能是奇数,也有可能是偶数
            // 比如aba,以b为中心,
            // 比如abba,要以bb中间的缝隙为中心才能找到正确的回文串
            // 所以不管是哪种,我们就都计算下,用max函数去最大的
            int len1 = expendAroundCenter(s,i,i);
            // 偶数回文串,为什么+1就是偶数
            // 因为偶数回文串的中心是两个字符,所以要从i和i+1开始扩展
            int len2 = expendAroundCenter(s,i,i+1);
            int len = Math.max(len1,len2);

            // end-start是为了记录最大回文串的长度,每次计算都要更新一下,确保留下最长的。
            if (len > end - start){
                // 如果当前回文串的长度大于之前的回文串长度,就更新start和end,为了记录下来最长的
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start,end+1);
    }

    public Integer expendAroundCenter(String s,int left,int right){
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            // 左右两边相等,继续扩展
            left--;
            right++;
        }
        // 遇到不相等或者到了边界,返回,计算长度
        return right - left - 1;
        // 之所以要-1,是因为上面的while循环中,left和right都多加了1
    }
}

到了这里,关于力扣刷题笔记-05 最长回文子串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【leetcode 力扣刷题】回文串相关题目(KMP、动态规划)

    题目链接:5. 最长回文子串 题目内容: 题目就是要我们找s中的回文子串,还要是最长的。其实想想,暴力求解也行……就是遍历所有的子串,同时判断是不是回文串,是的话再和记录的最大长度maxlen比较,如果更长就更新。时间复杂度直接变成O(n^3)。 优化的点在于,假设子

    2024年02月09日
    浏览(45)
  • 【力扣刷题】回文链表、环形链表、合并两个有序链表

    🐌个人主页: 🐌 叶落闲庭 💨我的专栏:💨 c语言 数据结构 javaEE 操作系统 Redis 石可破也,而不可夺坚;丹可磨也,而不可夺赤。 给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。 首先是要对该链表进行非空校验,若

    2024年02月07日
    浏览(41)
  • 力扣刷题笔记

    诸神缄默不语-个人CSDN博文目录 我以前刷过一波力扣,然后全忘了……从0开始的力扣复活赛! 以前刷题用的是Java,现在Java几乎忘光了,所以现在是Python 3 + Java双语选手。 以下题目按照力扣官方顺序排列。 449. 序列化和反序列化二叉搜索树 1281. 整数的各位积和之差 1749. 任意

    2024年02月14日
    浏览(38)
  • 力扣刷题笔记-07 整数反转

    狗看了都摇头的年纪,纯爱战士一败涂地。 temp用来保存个位数 res用来保存当前结果 123,取模运算,这样就可以获得最后一位。比如对123%10,得到temp=3. 判断res是不是溢出( 重点 ) 如果没有溢出,res扩大十倍,再加上个位数,就相当于是反转了。res = res * 10 + temp; 返回res。

    2024年02月08日
    浏览(39)
  • 力扣刷题笔记-06 N字形变换

    不要混日子,小心日子把你混了 对于题目的理解 比如说,我给一个字符串,LEETCODE,行数为3,然后按照N字形排列,就是下面这个排列方式。排列完之后正常读取,结果就是LCETOEED。这叫做N字形变换。 这个例子里给的行数就是3,往下排三行,然后往右往上走。 思路 边界情况

    2024年02月08日
    浏览(27)
  • 力扣刷题笔记-08 字符串转整数

    属于对字符串进行操作的问题 百无一用是情深 字符串里有数字,空格,正负号等,需要先过滤出来 在这道题目里,我们通常考虑字符串的组合是 “空格+正负号+数字”,一开始我想可能是“正负号+空格+数字”,但是这样的组合根本不可能是数字啊,没什么意义。 for循环

    2024年02月08日
    浏览(37)
  • 力扣刷题笔记-86 单链表的分解

    你说你会改变,但是你只是为了解决当时的冲突而讲的话。 给你一个链表头节点head和x,要求链表中所有小于x的节点都出现在大于或等于x的节点之前 例如:head = [1,4,3,2,5,2], x = 3; 输出:[1,2,2,4,3,5] 在合并两个链表的时候,是将两个链表合并成一个,拆分的时候,是将一个链表

    2024年03月13日
    浏览(28)
  • 647.回文子串 516.最长回文子序列

    力扣题目链接(opens new window) 给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。 示例 1: 输入:“abc” 输出:3 解释:三个回文子串: “a”, “b”, “c” 示例 2: 输入

    2024年01月19日
    浏览(42)
  • 最长回文子串&最长子串&第K大的数字&atoi

    解题思路:中心扩散法 中心扩散法 其实,我们知道,对于回文子串来说,是对称的。也就是说,从中心开始,往左扩散,往右扩散,一直去比较左右两边,如果一样,就再去往左扩散,往后扩散,直到结束,如果出现不相等的情况,那就说明不是回文子串。我们来举个例子

    2023年04月08日
    浏览(87)
  • 动态规划-最长回文子串

    突然觉得很有必要将学过的内容记录下来,这样后续在需要用到的时候就可以避免从头进行学习,而去看自己之前做过的笔记无疑是效率更高的方法。 而作为计算机专业的学生,纸质笔记无法很好的进行记录,像写代码、画图、画表都是很麻烦的,而且纸质的很容易丢,因此

    2024年04月14日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包