[M枚举] lc5. 最长回文子串(枚举+中心拓展+区间dp)「建议收藏」

[M枚举] lc5. 最长回文子串(枚举+中心拓展+区间dp)「建议收藏」文章目录1.题目来源2.题目解析方法一:枚举1.题目来源链接:lc5.最长回文子串2.题目解析方法一:枚举回文串一共有两种,即长度为奇数的回文串,长度为偶数的回文串。我们可以枚举回文串的中心(偶数长度回文串假想一个中心就行了),然后分别拿两个指针l=i-1,r=i+1向左右两边同时拓展,若s[l]=s[r]则,l–,r++。一直进行该操作,直到不等或一方到达边界位置。我们针对每一个枚举位置i,都考虑其两种情况,即偶数,奇数都考虑一遍,取个最大的就行了。

大家好,又见面了,我是你们的朋友全栈君。

1. 题目来源

链接:lc5. 最长回文子串

2. 题目解析

方法一:枚举

回文串一共有两种,即长度为奇数的回文串,长度为偶数的回文串。我们可以枚举回文串的中心(偶数长度回文串假想一个中心就行了),然后分别拿两个指针 l = i - 1r = i + 1 向左右两边同时拓展,若 s[l]=s[r] 则,l --, r ++。一直进行该操作,直到不等或一方到达边界位置。

我们针对每一个枚举位置 i,都考虑其两种情况,即偶数,奇数都考虑一遍,取个最大的就行了。

时间复杂度: O ( n 2 ) O(n^2) O(n2)

至于本问题,还有一些非常秀的方法。dp 在这也只能达到 O ( n 2 ) O(n^2) O(n2) 的时间复杂度,且还要开辟 dp 数组。

其中,字符串哈希+二分,貌似能够做到 O ( n l o g n ) O(nlogn) O(nlogn) 的时间复杂度。

至于那个,马拉车算法,之前简单看过,专门解决最长回文子串问题,时间复杂度能达到 O ( n ) O(n) O(n),不过可拓展性非常之低。

本题采用的中心拓展思想在别的问题中也能用到~

代码:

// 暴力直接算,即中心扩散,时间复杂度为O(n^2) 字符串最好能在1000以内的长度
// 动规可以算,时间复杂度为O(n^2) 
// 马拉车算法,专门解决最长回文子串问题,时间复杂度能达到O(n)

class Solution { 
   
public:
    string longestPalindrome(string s) { 
   
        int n = s.size();
        string res;
        for (int i = 0; i < n; i ++ ) { 
   
            // 处理回文串长度为奇数的情况
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) l -- , r ++ ;
            if (res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);   // 左闭右开区间

            // 处理回文串为偶数的情况
            l = i, r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]) l -- , r ++ ;
            if (res.size() < r - l - 1) res = s.substr(l + 1, r - l - 1);
        }
        return res;
    }
};

方法二:区间 dp

更新于 2021 年 4 月 16 日晚。字符串区间 dp 的题目比较少,经典有 lc 87 题,dfs 超时,区间 dp 可解,lc 87 是很难的一道题。

官方题解思路蛮不错的,三种方法都有涉及。

思路:

  • f[i][j] 表示 s[i : j] 能否构成回文串。
  • 当区间长度为 1 时,必然构成一个回文串,即 f[i][i] = true;
  • 字符串区间 dp 最重要的就是 枚举长度,要理解这个枚举顺序。
  • 枚举长度,再枚举左边界,通过长度确定右边界坐标。
  • 若右坐标合法,那么判断左右坐标对应字符是否相等,若不等则 f[i][j] 不构成回文串。否则,如果区间长度小于 3 的话,那么就直接是 f[i][j]=true,因为只有两个数字的话,f[i+1][j-1] 直接交换位置…造成状态的错误更新。否则区间长度大于等于三时,s[i : j] 首先两侧字符相等,那么 f[i][j] = f[i+1][j-1]。这两者是等价的。进行状态转移即可。

时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( n 2 ) O(n^2) O(n2)


很经典的一道题目,三种解法中的任一种都是非常经典且值得学习的。中心拓展、区间 dp 都是非常常用的思想,而马拉车不常用,但它却是能 O ( n ) O(n) O(n) 的解决该问题!日后再补吧,以前总结了,又忘了…

class Solution { 

public:
string longestPalindrome(string s) { 

int n = s.size();
if (n < 2) return s;
// f[i][j] 表示 s[i:j] 这一段是回文串,区间 dp
vector<vector<bool>> f(n, vector<bool>(n));
// 长度为 1 的串必然是回文的
for (int i = 0; i < n; i ++ ) f[i][i] = true;
// 最短的回文串长度就是 1,在这初始化 mx=0 的话会出错
// 可能整个串中都没有长度大于 2 的回文串,那么最后 substr() 的时候就会出错了,如 "ac"
int mx = 1, l = 0;      
for (int len = 2; len <= n; len ++ ) { 
      // 枚举子串长度
for (int i = 0; i < n; i ++ ) { 
         // 枚举左边界。根据长度得到右边界下标
int j = len + i - 1;                // [i, j] 有 j-i+1 个数
if (j >= n) break;                  // 右边界越界,左区间不需要再向右了,退出当前循环
if (s[i] != s[j]) f[i][j] = false;  // [i,j] 不构成回文串
else { 

// 等价 if (len < 3) 因为只有两个数字的话,f[i+1][j-1] 直接交换位置...
if (j - i < 3) f[i][j] = true;  // [i,j] 长度小于等于 2 只要s[i]==s[j]就构成回文串
else f[i][j] = f[i + 1][j - 1]; // 可能构成回文串,取决于 s[i+1:j-1] 是否能构成回文串
}
if (f[i][j] && j - i + 1 > mx) { 

mx = j - i + 1;
l = i;
}
}
}
return s.substr(l, mx);
}
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164020.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • VBS 代码合集(慎用,好玩)

    VBS 代码合集(慎用,好玩)玩玩就好啦记得关注哦一、你打开好友的聊天对话框,然后记下在你QQ里好友的昵称,把下面代码里的xx替换一下,就可以自定义发送QQ信息到好友的次数(代码里的数字10改一下即可).xx.vbs=>=—————————————————————————OnErrorResumeNextDimwsh,yesetwsh=createobject(“wscript.shell”)fori=1

  • datagripmac的激活码2021(JetBrains全家桶)

    (datagripmac的激活码2021)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~M…

  • JVM调优工具总结

    JVM调优工具总结一、jps:虚拟机进程状况工具它可以列出正在运行的虚拟机进程,并显示虚拟机执行主类(MainClass,main()函数所在的类)名称以及正在运行的本地虚拟机唯一ID(LVMID);它是使用率最高的一个JDK命令行工具,因为其他的命令行工具都需要输入查询到的ID来确定要监控的是哪一个虚拟机进程。命令格式:jps[options][hostid]选项作用-q只…

  • Android游戏引擎_2d游戏引擎

    Android游戏引擎_2d游戏引擎Android游戏引擎汇总1.AndEngine简介:AndEngine基于libGDX框架开发,使用OpenGLES进行图形绘制。同时继承了BOX2D物理引擎,因此能实现一些较为复杂的物理效果。在Rokon停止更新以后,AndEngine成为Android最为流行的2D游戏引擎优点:(1)高效:在大运算量好事情况下,使用C/C++本地代码进行开发。比如物理引擎或

  • MySQL中 如何查询表名中包含某字段的表

    MySQL中 如何查询表名中包含某字段的表

  • mybatis trim标签

    mybatis trim标签mybatis的trim标签一般用于动态sql语句中去除多余的and关键字,逗号等以下是trim标签中涉及到的属性:属性描述prefix给sql语句拼接的前缀suffix给sql语句拼接的后缀prefixOverrides去除前缀suffixOverrides去除后缀案例trim实现insert into ()values()<insert id=”insert” parameterType=”InfoStudent”> .

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号