LeetCode 5. 最长回文子串
2020-05-22 16:11:50来源:博客园 阅读 ()
LeetCode 5. 最长回文子串
我的LeetCode:https://leetcode-cn.com/u/ituring/
我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii
LeetCode 5. 最长回文子串
题目
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设?s 的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
本题有三种思路解法:
- dp动态规划
- 中心扩展
- Manacher/马拉车算法
其中,前两种时间复杂度都是\(O(n^{2})\),最后一种是\(O(n)\)的,目前最优解;
思路1-dp动态规划
思路解析:dp的思路是若\([i] == [j]\),那么让\([i, j]\)是回文就必须有\([i + 1] == [j - 1]\);
即dp的动态方程为:
\[dp[i, j] = dp[i + 1, j - 1] and ([i] == [j] || j - i < 3) \]
对于\(j - i < 3\)的解释:当最后的只剩单个字符时,作为回文的中心字符免验证;
算法复杂度:
- 时间复杂度: $ {\color{Magenta}{\Omicron\left(n^{2}\right)}} $
- 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
思路2-中心扩展
思路解析:首先把字符串的所有连续相等的字符都压缩看为一个字符,那么对每一个字符尝试左右扩展回文长度即可;
核心思想:将所有连续相等的字符看为回文的最中心字符,避免了对奇偶数的区别计算;
算法复杂度:
- 时间复杂度: $ {\color{Magenta}{\Omicron\left(n^{2}\right)}} $
- 空间复杂度: $ {\color{Magenta}{\Omicron\left(1\right)}} $
思路3-Manacher/马拉车算法
待研究...
算法复杂度:
- 时间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
算法源码示例
package leetcode;
/**
* @author ZhouJie
* @date 2019年12月10日 下午2:30:25
* @Description: 5. 最长回文子串
*
*/
public class LeetCode_0005 {
}
class Solution_0005 {
/**
* @author ZhouJie
* @date 2019年12月10日 下午3:07:18
* @Description: TODO(方法简述)
* @return String
* @UpdateUser-UpdateDate:[ZhouJie]-[2019年12月10日 下午3:07:18]
* @UpdateRemark:1-动态规划
*
*/
public String longestPalindrome_1(String s) {
int len = 0;
if (s == null || (len = s.length()) < 2) {
return s;
}
boolean[] p = new boolean[len];
int[] range = new int[2];
for (int i = len - 1; i >= 0; i--) {
for (int j = len - 1; j >= i; j--) {
// j-i考虑到 像OO和OHO最后中心的奇偶问题
p[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || p[j - 1]);
if (p[j] && (j - i > range[1] - range[0])) {
range[0] = i;
range[1] = j;
}
}
}
return s.substring(range[0], range[1] + 1);
}
/**
* @author ZhouJie
* @date 2019年12月10日 下午3:34:44
* @Description: TODO(方法简述)
* @return String
* @UpdateUser-UpdateDate:[ZhouJie]-[2019年12月10日 下午3:34:44]
* @UpdateRemark:2-中心扩展--优化后
*
*/
public String longestPalindrome_2(String s) {
if (s == null || s.length() < 2) {
return s;
}
int[] range = new int[2];
char[] cs = s.toCharArray();
for (int i = 0; i < cs.length; i++) {
// 把回文看成中间部分都是同一字符且左右对称,寻找下一个与当前字符不同的位置
i = fastMove(cs, i, range);
// 若剩余长度不足已知最大长度的一半时,直接跳出循环
// 剩余长度的下一个起始计算位置为i+1,以为i+1为中心的剩余最长回文为(length-1-(i+1))*2+1
// 即 (lenght-i-2)*2+1,一只的最大长度为range[1]-range[0]+1
// 所以判定条件为 (lenght-i-2)*2+1<range[1]-range[0]+1
// 即(lenght-i-2)*2<range[1]-range[0]
if ((cs.length - i - 2) * 2 < (range[1] - range[0])) {
break;
}
}
return s.substring(range[0], range[1] + 1);
}
private int fastMove(char[] cs, int low, int[] range) {
int high = low;
int len = cs.length;
// 寻找下一个与low不等的字符
while (high < len - 1 && cs[high + 1] == cs[low]) {
high++;
}
int nextI = high;
// 开始校验左右扩散校验
while (low > 0 && high < len - 1 && cs[low - 1] == cs[high + 1]) {
low--;
high++;
}
if (high - low > range[1] - range[0]) {
range[0] = low;
range[1] = high;
}
return nextI;
}
/**
* @author: ZhouJie
* @date: 2020年5月22日 下午9:47:36
* @param: @param s
* @param: @return
* @return: String
* @Description: 3-Manacher算法--待研究
*
*/
public String longestPalindrome_3(String s) {
return null;
}
}
原文链接:https://www.cnblogs.com/izhoujie/p/12939960.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:JDK(JAVA环境)安装
- LeetCode 287. 寻找重复数 2020-05-31
- LeetCode 21. 合并两个有序链表 2020-05-22
- LeetCode 面试题55 - I. 二叉树的深度 2020-05-22
- LeetCode 104. 二叉树的最大深度 2020-05-22
- LeetCode 面试题53 - I. 在排序数组中查找数字 I 2020-05-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash