动态规划-最长回文子串

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


突然觉得很有必要将学过的内容记录下来,这样后续在需要用到的时候就可以避免从头进行学习,而去看自己之前做过的笔记无疑是效率更高的方法。

而作为计算机专业的学生,纸质笔记无法很好的进行记录,像写代码、画图、画表都是很麻烦的,而且纸质的很容易丢,因此还是进行电子笔记记录更佳。

那么选择用博客还是云笔记呢?私以为选择更为公开的博客,可以更加驱动自己进行详细的记录和进行浅显易懂的讲解,从而避免自己某些时候滥竽充数的行为。

原题描述

5. 最长回文子串
给你一个字符串 s,找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。

示例 1:
输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。

示例 2:
输入:s = “cbbd”
输出:“bb”

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

解答

中心移动

思想

对于这个题来说,进行最长回文子串的判断,首先想到的就是遍历所有的回文子串,然后记录最长的回文子串及其长度
那么如何遍历这些回文子串?由于回文子串的遍历需要从中心往四周进行遍历,所以需要遍历所有的回文中心,但是回文中心会有以下两种情况。

  1. 中心只有一个字符的总长度为奇数的情况,例如aba
  2. 中心会有两个字符的总长度为偶数的情况,例如abba

设i, j为中心点。那么对于中心只有一个字符的情况1来说,i=j;对于中心会有两个字符的情况2来说,j=i+1。
动态规划-最长回文子串,算法题,动态规划,算法

那其实就很简单了,让i、j进行这种遍历,在遍历的时候分别设置两个指针lr进行左右的拓展,如果是回文子串就记录,否则在当下的回文中心下已经不可能有更长的回文了,进行下一次的回文中心遍历即可。

代码实现

C++代码:

class Solution {
public:
    string longestPalindrome(string s) {

        int len = s.length();
        if(len < 2)  // 特殊情况处理
            return s;

        int i=0, j=1;
        int maxLen = 1, startPos = 0;
        
        while(i<len-1 && j<len){
            if(s[i] == s[j]){
                int left = i-1, right = j+1;
                while(left>=0 && right<=len-1 && s[left]==s[right]){
                    left--;
                    right++;
                }
                if(right-left-1>maxLen){
                    maxLen = right-left-1;
                    startPos = left+1;
                }
            }

            if(i!=j)
                i++;
            else
                j++;
        }
        
        return s.substr(startPos, maxLen);
    }
};

这里在进行实现的时候,有进行一些小tips优化:

  1. i0开始到len-2j1开始到len-1,也就是省略了i=0,j=0i=len-1,j=len-1的情况。
    因为这两种情况其实也只能判断一个长度为1的回文子串,这种情况在中间的时候随便都能判断出来。最极端情况下,例如ab这样长度为2的非回文串,由于startPosmaxLen的设置,最后返回的也是a,不会出问题。
  2. 中途对最长的回文子串进行记录的时候,不要直接进行截断来存字符串,而是记录开始的下标和长度,这样最后只截取一次,避免性能开销。

复杂度分析

时间复杂度

令字符串长度为n,中心只有一个字符的有n种情况,中心有两个字符的有n-1种情况。总共有2n-1种中心情况。
对于每次的中心情况进行遍历的时候,由于是向两边扩展,最多不超过n/2
相乘,也就是O(n^2)的时间复杂度。

空间复杂度

没有开辟额外空间,O(1)

动态规划

动态规划说实话,在这个题目并不合适,还不如上面的中心移动的方法。因为动态规划相比来说会有额外的二维数组的空间开销。

思想

用最经典的动态规划思考方式来进行。设置一个二维数组dp[n][n],其中dp[i][j]代表s[i...j]是不是回文子串,是的话为true,不是为false

  1. 最优子结构
    s[i...j]是不是回文子串,取决于s[i+1...j-1]是不是回文子串和s[i]是否与s[j]相同。
  2. 状态转移方程

d p [ i ] [ j ] = = { d p [ i + 1 ] [ j − 1 ] , s [ i ] = = s [ j ] f a l s e , s [ i ] ! = s [ j ] dp[i][j] = = \begin{cases} dp[i+1][j-1], & s[i]==s[j]\\ false, & s[i]!=s[j] \\ \end{cases} dp[i][j]=={dp[i+1][j1],false,s[i]==s[j]s[i]!=s[j]

  1. 边界处理
    i=j的时候,长度为1,必定是回文子串,dp[i][j]=true

代码实现

C++代码

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length();
        // 特殊处理
        if(len < 2)
            return s;
        
        int maxLen = 1, begin = 0;

        vector<vector<bool>> dp(len, vector<bool>(len, false));
        for(int i=0; i<len; i++)
            dp[i][i] = true;
        
        for(int j=1; j<len; j++){
            for(int i=0; i<j; i++){ // 注意i从0开始
                if(s[i] != s[j])
                    dp[i][j] = false;
                else{
                    if(j-i < 3)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i+1][j-1];
                }
                if(dp[i][j] == true && j-i+1>maxLen){
                    begin = i;
                    maxLen = j-i+1;
                }
            }
        }
        return s.substr(begin, maxLen);
         
    }
};

tips:
当s[i] == s[j]的时候,先进行了j-i<3的判断,这种情况是子串的长度<=3的情况,在这种情况下s[i]=s[j],不管长度为2还是3,都是回文子串,直接返回true。

复杂度分析

时间复杂度

O(n^2)

空间复杂度

开辟了一个二维数组,O(n^2)

2024/03/31:
希望后面在刷算法题的时候能够坚持下来,在搞懂一个算法题之后通过博客的方式来做笔记,这样后面在warmup的时候很快就能上手,避免重复的0到1的思考。文章来源地址https://www.toymoban.com/news/detail-850571.html

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

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

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

相关文章

  • day57|动态规划17-最长回文子串问题

    回文子串:强调连续 回文子序列:不强调连续 暴力思路:三层for循环 双指针思路: 动态规划 dp数组 dp[i][j]: 根据字符串的形式和所解决的问题确定dp数组的形式和含义。 递归公式 (分情况讨论) 2.1 如果 i j 2.2 如果 j-i 1 2.3 如果 j-i1: 此时依赖于dp[i+1][j-1]是不是一个回文子

    2024年02月09日
    浏览(43)
  • 【算法】算法学习七:动态规划 | 背包问题 | 最长公共子串(含源代码)

    背包问题是一种经典的组合优化问题,通常有两个版本:0-1背包问题和无限背包问题。 0-1背包问题是指给定一个背包容量和一组物品,每个物品有自己的重量和价值,要求在不超过背包容量的情况下,选择一些物品放入背包,使得物品的总价值最大化。每个物品只能选择放入

    2024年02月09日
    浏览(48)
  • 【算法沉淀】最长回文子串

     🎉🎉欢迎光临🎉🎉 🏅我是苏泽,一位对技术充满热情的探索者和分享者。🚀🚀 🌟特别推荐给大家我的最新专栏 《数据结构与算法:初学者入门指南》📘📘 希望能和大家一起学习!共同进步! 这是苏泽的个人主页可以看到我其他的内容哦👇👇 努力的苏泽 http://su

    2024年03月12日
    浏览(46)
  • 算法刷题|647.回文子串、516.最长回文子序列

    题目:给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。 d

    2024年02月17日
    浏览(51)
  • 最长子串和回文子串相关的算法题解

    中等 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2: 输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。 示

    2024年02月19日
    浏览(41)
  • 【算法Hot100系列】最长回文子串

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月04日
    浏览(37)
  • 动态规划 回文子串

    647. 回文子串 双指针法: 遍历回文中心----一个回文中心----两个回文中心 遍历边界,找出回文中心, 其实还是变相的找回文中心 动态规划: 4. dp[i][j]:表示区间范围[i,j] (注意是左闭右闭)的子串是否是回文子串,如果是dp[i][j]为true,否则为false 5. 当s[i]与s[j]不相等,那没

    2024年02月15日
    浏览(44)
  • 最长公共子串(动态规划)

    查找两个字符串a,b中的最长公共子串_牛客题霸_牛客网 1.找a 和 b 的最长公共子串实际上是在a的子串和b的子串中找最长公共子串 ins[i][j]实际上记录的就是 以a的第i个字符和以b的第j个字符结尾的子串中存在的最长公共子串的长度 接下来我们举个例子: a: abcabcde b: abcd ins[1][1]

    2023年04月12日
    浏览(49)
  • 动态规划-最长的回文序列

    该题是lintcode上 667 · 最长的回文序列,该题的解题思路亦是参考了九章侯老师的解题思路给出。 给一字符串 s, 找出在 s 中的最长回文子序列的长度. 你可以假设 s 的最大长度为 1000. 输入: “bbbab” 输出: 4 解释: 一个可能的最长回文序列为 “bbbb” 输入: “bbbbb” 输出:

    2024年02月09日
    浏览(47)
  • 力扣第131题 分割回文串 c++ 回溯+简单 动态规划(是否为回文子串)

    131. 分割回文串 中等 相关标签 字符串   动态规划   回溯 给你一个字符串  s ,请你将   s   分割成一些子串,使每个子串都是  回文串  。返回  s  所有可能的分割方案。 回文串  是正着读和反着读都一样的字符串。 示例 1: 示例 2: 提示: 1 = s.length = 16 s  仅由小写

    2024年02月07日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包