给你一个字符串 s，找到 s 中最长的回文子串
示例：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
思路一：动态规划
先求出所有子串是否是回文串并添加标记true false ,然后在对比拿到最长的那个子串的起始位置和长度后 就可以得到最长回文子串
假设cs字符串"babad",它的长度是n , dp是大小为n* n的二维数组，dp[i][j] 表示cs[i,j]是否为回文串，存储true、false
如何求出dp[i][j]的值？通过最短子串分析可以得知有两种情况
首先要知道cs[i][j] 的长度是 int length = j - i + 1
第一种： length <= 2
如果cs[i,j] 的长度 length = 2 时，dp[i][j] = cs[i] == s[j]
如果cs[i,j]的长度 length < 2 那此时 length = 1 跟length = 2一样的
第二种： length > 2
如果cs[i+1,j-1]是回文子串，并且cs[i]等于cs[j] ,那么cs[i,j] 就是回文子串
所以dp[i][j] = (dp[i+1,j-1] && cs[i]==cs[j] )
动态规划：
时间复杂度O(n^2)
空间复杂度O(n^2)
如果用暴力解法：时间复杂度O(n^3) 空间复杂度O(1) ,所以此解法比暴力法稍好，比暴力法好在 动态规划在时间复杂度是O(n^2)O(1) 暴力是O(n^2)O(n), 其中n^2是用来列举子串， n是判断是否是回文子串用的时间，所以动态规划优化的点就是判断回文子串这个逻辑点 但是空间复杂度上升了 可以认为是在 空间换时间
class Solution {
//思路：动态规划
public String longestPalindrome(String s) {
//0.边界判断
if(s==null) return null;
//1.定义解题需要用到的数据结构
char[] cs = s.toCharArray();
if(cs.length <= 1) return s;
//2.动态规划通过遍历得到最长回文子串
boolean dp[][] = new boolean[cs.length][cs.length];
int maxLen = 1;//最长回文串长度
int begin = 0;//最长回文串开始索引
//遍历方式： 从上到下 i从大到小 从左到右 j从小到大
for(int i = cs.length - 1; i >= 0;i--) {
// j = i 是因为 j的值要大于等于i的值才有意义
for(int j = i;j < cs.length;j++) {
//[i,j]范围字符串长度
int len = j - i + 1;
if(len > 2) {
//[i+1,j-1]是回文串 && i位置字符和j位置字符相同，那么[i,j]就是回文串
dp[i][j] = ((dp[i+1][j-1])&&(cs[i]==cs[j])) ?true:false;
}else {//len <= 2
//i位置字符和j位置字符相同 就是回文串
dp[i][j] = (cs[i]==cs[j])?true:false;
}
//[i,j]是回文串 && 回文串的长度大于已知最大长度，就更新最大长度和回文串起始位置
if(dp[i][j] && len > maxLen) {
begin = I;
maxLen = len;
}
}
}
//3.返回最长回文子串
return new String(cs,begin,maxLen);
}
}
思路二：扩展中心法
通过找到一个点为标准向左右两个方向扫描扩展，直到不是回文串结束；首先能想到的是以一个字符来做基准扫描，但是分析后发现这样扫描出来的回文串全是奇数，所以要想用这种方法就需要再加一个标准 ？ 那可以考虑把两个字符中间的间隙当做一个虚拟标准，这样得到的回文串都是偶数 至此就覆盖了所有的情况
当我们知道了所有的回文串 只需要再对比出最大的长度和起始位置 就能拿到这个回文子串了！
时间复杂度O(n^2)
空间复杂度O(1)
class Solution {
public String longestPalindrome(String s) {
if(s==null) return s;
char[] cs = s.toCharArray();
//空串、单字符 最长回文串就是本身
if(cs.length <= 1) return s;
int maxLen = 1;//最长回文串长度
int begin = 0; //最长回文串开始索引
//从倒数第二位开始遍历，这样可以避免边界判断
for(int i = cs.length - 2; i >= 1; i--) {
//处理索引和间隙两种情况，索引扫描结果全部是奇数，间隙扫描结果全部是偶数，这样就覆盖了所有情况
//以索引位中心左右扩展
int len1 = palindrome(cs,i-1,i+1);
//以字符右边的间隙为中心左右扩展
int len2 = palindrome(cs,i,i+1);
int len = Math.max(len1,len2);
if(len > maxLen) {
maxLen = len;
begin = i - ((maxLen-1)>>1);
}
}
//处理以0号字符右边间隙为中心
if(cs[0]==cs[1]&&maxLen<2) {//成立cs[0,1] 就是最长的回文子串
maxLen = 2;
begin = 0;
}
return new String(cs,begin,maxLen);
}
//计算回文串的长度 cs数组 l左边标识 r右边标识
private int palindrome(char[] cs,int l, int r) {
//注意判断顺序不能错
while(r < cs.length && l >= 0 && cs[l]==cs[r]) {
l--;
r++;
}
return r-l-1;
}
}
优化扩展中心
babbbabaa
之前是以一个标准左右扩展，直到不是回文串结束
现在可以优化为从单字符变为多字符 给标准位置 i 向左 L 向右R ，从数组左侧开始扫描 来到标准位i 先向右扫描跟自己相同的字符，每遇到相同的R就移动一步，不同就停止，此时我们把i ~ R之间的子串(例如：bbb) 当做是标准位向左右扩展
核心逻辑：
找到右边第一个不等于s[i] 的字符，记为位置R,i左边的位置记为L
R作为下一次的i
由L开始向左，R开始向右扩展，找到最长的回文子串
时间复杂度O(n^2)
空间复杂度O(1)
class Solution {
public String longestPalindrome(String s) {
if(s==null) return s;
char[] cs = s.toCharArray();
//空串、单字符 最长回文串就是本身
if(cs.length <= 1) return s;
int maxLen = 1;//最长回文串长度
int begin = 0; //最长回文串开始索引
int i = 0;
//从左边开始遍历
while(i < cs.length) {
int r = I;
int l = i - 1;
//找到右边第一个不等于cs[i]的位置
while(++r < cs.length && cs[i]==cs[r]);
//r会成为新的i
i = r;
//从l向左，从r向右扩展
while(l>=0 && r<cs.length && cs[l]==cs[r]){
l--;
r++;
}
//扩展结束后cs(L,R)就是这轮找到的最大回文子串
int len = r - l - 1;
if(len > maxLen) {
maxLen = len;
begin = l + 1;
}
}
return new String(cs,begin,maxLen);
}
}
思路三 : 马拉车算法
先对原始字符数组做一次预处理，通过预处理找到逻辑点 也就是利用回文串的规律找到计算方法；从而求出每个字符的回文串长度，最终对比找到最长回文串返回
预处理规则：
- 在头部和尾部分别添加两个原字符不包含的字符
- 在索引1位置和所有原字符后面都分别添加一个特殊字符，到此就生成一个新的字符数组cs
比如:'^#a#b#b#a#b#a#$' - 至此你就会发现每一个原始字符都有了自己的回文串，
#a##b#
预处理结果示例.png
初始化m数组长度和cs相同，m[i] 的含义是cs[i] 为扩展中心的最大回文子串的长度(不包含#字符)
得出最大回文子串在原始字符串中的初始索引：(i-m[i])>>1
操作步骤：
设 l li c i r,
l:以c为中心的回文串左边界索引
r:以c为中心的回文串右边界索引
c:回文串中心索引
li: cs[li,c,i]回文串左边界索引
i: cs[li,c,i]回文串右边界索引
设 m 、cs数组，cs表示已经预处理过的数组，m表示以cs中某一个字符为中心的回文串长度的一半
cs[l,r]是以c为中心的最大回文串；i li是以c为中心对称即cs[li,i]是回文串
所以,Manacher算法的关键在于求出M数组
i < r
以下逻辑中的 1 3 5 是举例而已是为了能够更好的分析问题，不要纠结
- 如果已知 m[li] == 1 此时 i + m[li] < r, 由于回文串的对称性得出 m[i] = m[li] 即 m[i] = 1
m[li] == 1的情况.png
- 如果已知 m[li] == 3 此时 i + m[li] == r, m[i]至少是m[li],也就是说 至少是3
m[li] == 3的情况.png
- 如果已知 m[li] == 5 此时 i + m[li] > r, m[i]至少是r-i 也就是至少是3，接下来利用扩展中心法以i为中心计算出m[li]
扩展中心：当i+m[i] > r时 更新 c 、r；c = I；r = i + m[I]
m[li] == 5的情况.png
i == r
-
直接利用扩展中心法以i为中心计算出m[i]
i == r的情况.png
i > r 是不合理的情况不必考虑
时间复杂度O(n)
空间复杂度O(1)
class Solution {
/**
思路：马拉车算法
设 l li c i r,
l:以c为中心的回文串左边界索引
r:以c为中心的回文串右边界索引
c:回文串中心索引
li: cs[li,c,i]回文串左边界索引
i: cs[li,c,i]回文串右边界索引
cs[l,r]是以c为中心的最大回文串；i li是以c为中心对称即cs[li,i]是回文串
i < r
如果已知 m[li] == 1 此时 i + m[li] < r, 由于回文串的对称性得出 m[i] = m[li] 即 m[i] = 1
如果已知 m[li] == 3 此时 i + m[li] == r, m[i]至少是m[li],也就是说 至少是3
如果已知 m[li] == 5 此时 i + m[li] > r, m[i]至少是r-i 也就是至少是3，接下来利用扩展中心法以i为中心计算出m[li]
扩展中心：
当i+m[i] > r时 更新 c 、r
c = i
r = i + m[i]
i == r
直接利用扩展中心法以i为中心计算出m[i]
i > r 是不合理的情况不必考虑
*/
public String longestPalindrome(String s) {
//0.边界处理
if(s==null) return s;
//1.定义需要的数据结构
char[] oldCs = s.toCharArray();
if(oldCs.length <= 1) return s;
char[] cs = preprocess(oldCs);//加工后的数组
int[] m = new int[cs.length];//构建m数组
int c = 1;//回文串中心索引
int r = 1;//回文串右边边界索引
int lastIdx = m.length - 2;//数组遍历边界
int idx = 0;//记录每次找到的最长回文串的中心索引
int maxLen = 0;//最长回文子串的长度
int begin = 0;//最长回文子串开始索引
//2.遍历求出 m[i],i从2开始因为m数组前两位的值肯定都是0,没有遍历的必要
for(int i = 2;i < lastIdx;i++) {
//2.1 i < r
if(i < r) {
//li的计算公式: (c*2)-i 因为cs[li,c,i] --> (li+i)/2 = c
int li = (c<<1)-i;
if(i+m[li] <= r) {
//<= 就说明以i为中心的回文串的最右索引是在以c为中心的回文串范围内的，所以此时m[i]的值至少跟m[li]相等
m[i] = m[li];
}else {
//> m[i]的值至少是 r和i的差值
m[i] = r - i;
}
}
//2.2 i = r 直接扩展中心法
//假设 i=8 m[i]=4 那么右侧边界的下一个索引就是13 i+m[i]+1
//假设 i=8 m[i]=4 那么左侧边界的前一个索引就是3 i-m[i]-1
while(cs[i+m[i]+1] == cs[i-m[i]-1]){
m[i]++;
}
//2.3 更新c r
if(i+m[i]>r){//大于说明已经超出当前最大回文长度，所以就转移中心位置和右边界
c = i;
r = i + m[i];
}
//2.4 记录当前最长回文串的长度和中心索引
if(m[i] > maxLen){
maxLen = m[i];
idx = i;//记录每次找到的最长回文串的中心索引
}
}
//3.返回结果
begin = (idx-maxLen)>>1;
return new String(oldCs,begin,maxLen);
}
//预处理数组
private char[] preprocess(char[] oldCs) {
//初始化 预处理规则前面多两个字符 尾部多1个字符 每个字符后面多加一个字符
char[] cs = new char[(oldCs.length<<1)+3];
//马拉车算法 特殊位置字符处理:头尾加特殊字符且与中间字符不能相同
cs[0] = '^';
cs[1] = '#';
cs[cs.length-1] = '$';
//循环在每个字符后面追加一个字符，可以和老字符数组中的字符相同，但为了方便区分最好不同
for(int i = 0;i < oldCs.length;i++) {
//两数组之间的下标规律 (i+1)*2,此规律设计是马拉车算法的基础
int idx = (i+1)<<1;
cs[idx] = oldCs[i];
cs[idx+1] = '#';
}
return cs;
}
}
执行结果.png
网友评论