【算法沉淀】最长回文子串

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

 🎉🎉欢迎光临🎉🎉

🏅我是苏泽,一位对技术充满热情的探索者和分享者。🚀🚀

🌟特别推荐给大家我的最新专栏《数据结构与算法:初学者入门指南》📘📘

希望能和大家一起学习!共同进步!

这是苏泽的个人主页可以看到我其他的内容哦👇👇

努力的苏泽http://suzee.blog.csdn.net

【算法沉淀】最长回文子串,《数据结构与算法:初学者入门指南》📘📘,算法

5. 最长回文子串

提示

给你一个字符串 s,找到 s 中最长的回文

子串

如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"
输出:"bb"

提示:

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

【算法沉淀】最长回文子串,《数据结构与算法:初学者入门指南》📘📘,算法

题目解析: 给定一个字符串s,需要找到s中最长的回文子串。回文字符串是指正序和反序都相同的字符串。

思路如下:

  1. 初始化两个指针left和right,分别表示当前考虑的子串的左右边界。初始时,left=0,right=0。
  2. 使用一个变量max_len来记录最长回文子串的长度,初始值为0。同时使用一个变量start来记录最长回文子串的起始位置,初始值为0。
  3. 使用两层循环来枚举所有可能的子串。外层循环使right指针从0到字符串末尾,内层循环使left指针从0到right。
  4. 对于每个子串,检查其是否为回文。如果是,并且其长度大于max_len,则更新max_len和start。
  5. 在检查子串是否为回文时,可以使用双指针法。初始化两个指针p1和p2,分别指向子串的首尾。如果p1和p2指向的字符相同,则将p1向右移动一位,p2向左移动一位。如果p1和p2指向的字符不同,则说明该子串不是回文。
  6. 在遍历完所有子串后,最长回文子串的起始位置为start,长度为max_len。

【算法沉淀】最长回文子串,《数据结构与算法:初学者入门指南》📘📘,算法

public class Solution {
    public String longestPalindromicSubstring(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }
}

【算法沉淀】最长回文子串,《数据结构与算法:初学者入门指南》📘📘,算法文章来源地址https://www.toymoban.com/news/detail-838968.html

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

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

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

相关文章

  • 算法打卡day49|动态规划篇17| Leetcode 647. 回文子串、516.最长回文子序列

    Leetcode 647. 回文子串 题目链接:647. 回文子串 大佬视频讲解:647. 回文子串视频讲解  个人思路  这道题的dp数组有点难找到关联,以至于递归关系也不好找,所以看题解吧... 解法 动态规划 动规五部曲: 1.确定dp数组(dp table)以及下标的含义 一般在定义dp数组的时候 会根据题

    2024年04月22日
    浏览(46)
  • 【算法题】动态规划中级阶段之最长回文子串、括号生成、跳跃游戏

    动态规划(Dynamic Programming,简称 DP)是一种解决多阶段决策过程最优化问题的方法。它是一种将复杂问题分解成重叠子问题的策略,通过维护每个子问题的最优解来推导出问题的最优解。 动态规划的主要思想是利用已求解的子问题的最优解来推导出更大问题的最优解,从而

    2024年02月12日
    浏览(43)
  • 【经典算法】LeetCode 5: 最长回文子串(Java/C/Python3实现含注释说明,Medium)

    标签(题目类型):回文串、动态规划 原题:LeetCode 5 思路 Dynamic Programming(DP) 动态规划是一种将问题分解成子问题并分别计算的优化技术。对于回文子串,我们可以使用动态规划来解决。 对于一个子串而言,如果它是回文串,并且长度大于 2,那么将它首尾的两个字母去除之后

    2024年04月14日
    浏览(66)
  • 647.回文子串 516.最长回文子序列

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

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

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

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

    给你一个字符串 s ,找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。 示例 1: 示例 2: 1、动态规划算法 解题思路 (1)考虑 回文串的性质 :若一个子串是回文串并且 长度大于2 ,则将其 首尾两个字母去除 后,该子串仍然是一

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

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

    2024年04月14日
    浏览(37)
  • 【LeetCode刷题】最长回文子串

    📝个人主页:爱吃炫迈 💌系列专栏:数据结构与算法 🧑‍💻座右铭:道阻且长,行则将至💗 题目:最长回文子串 思路一:暴力 枚举每一个子串,找回文串,然后通过比较,找出最长的回文串。 会超时 学习更多的JavaScript字符串方法,例如上面代码中用到的 split() , joi

    2023年04月23日
    浏览(57)
  • leetcode 5 最长回文子串

    题目 给你一个字符串 s,找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。 示例 输入:s = “babad” 输出:“bab” 解释:“aba” 同样是符合题意的答案。 解析 这道题和之前的那道回文的很像:647回文子串,求个数,解法还是动态

    2024年02月10日
    浏览(54)
  • 【LeetCode】5 . 最长回文子串

    思想 「中心扩散法」的基本思想是:遍历每一个下标,以这个下标为中心,利用「回文串」中心对称的特点,往两边扩散,看最多能扩散多远。 枚举「中心位置」时间复杂度为 O(N),从「中心位置」扩散得到「回文子串」的时间复杂度为 O(N),因此时间复杂度可以降到 O(N 2

    2024年02月10日
    浏览(31)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包