题目
有这么一个字符串s，找到s中最长的回文子串，假设s的长度最大值是1000.
所谓回文就是中心轴对称的字符串。
示例
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
思路1
回文，可以理解为正向看和逆向看都一样的字符串。那这样的话就可以弄正向和反向字符串各一，作为一个矩阵的两个坐标轴。如果字符一样就在左上角的基础上加一，否则就置0。这样的话就能得到一个最长的回文字符串子串，但是如果整个字符串在对称的位置上正好有两个对称的子串，那么此方法可能得出错误的答案，于是，在每次得出更长的回文子串的时候就应该验证它是不是回文，毫无疑问这增加了时间复杂度，于是它超时了，达到了3次方级别。不过确实是该问题的一个解法。
思路2
第二种是动态规划算法。动态规划算法的关键在于能找出问题和子问题之间的关系，在本题中就是要判断子串s[i,j]是不是子串，首先要判断s[i]和s[j]是不是相等，如果不等，那么s[i,j]绝对不是回文，如果想等就要转去判断s[i+1,j-1]是不是回文。
最低级的子问题是字符串中的每个字符是一个回文字符串。接下来是2个相邻元素的时候，它是基于1个字符的子问题的解的基础上的，这个就需要遍历一趟了。接下来的问题就是上面提到的递归式中了。
因为动态规划算法是靠画表格解决问题的，所以该表格的每个单元格代表是的s[i,j]是不是回文子串，所以它的横纵轴代表的是字符在字符串中的坐标。其实这种表格只用了一半，就是右上三角。
思路3
可以发现每个回文子串都是中心轴对称的。具体为或者关于某个字符对称，或者关于某一对相同的相同字符的中间间隙对称，于是连间隙带字符就有n-1+n=2n+1个中心轴了，所以可以以每个轴心向两边扩展。这个时间复杂度也是O(n^2)。你可以这样形象地想象，轴心上面有一个能伸长的棒子，并且棒子的中心就是这个轴心，不断地旋转，棒子的两头不遇到不同的就不停下来。
思路4
manacher算法，也有人称它是马拉车算法，我觉得现在网上有关这个算法的文章写得不通俗，于是我重新用俗话阐述一遍，希望能把它说明白。它是把这个字符串的每个间隙都插入了一个占位符，包括字符串首外侧，这样的话字符串中的字符加上占位符总共有2n+1个字符，这样做的目的是为了用统一的方式来处理奇数回文子串和偶数回文子串。然后它又用了一个数组P来存储以每个字符为对称轴的回文字符串的半径，不包括对称轴它自己。算法的整个过程都是在不断地计算这个数组P中的每个元素的值。那么当前正在处理的以C为对称轴的回文子串是C右侧暂时的任何的已经计算出对称半径并且对称半径加上下标所得到的右侧边界的下标还没有超过以C为对称轴的那个回文字符串的右侧边界的回文子串。我在想它在判定中心轴半径的时候难道不需要遍历一下吗？那么它是怎么遍历的呢？没办法就是左右两边比较得到的。因为C右侧对称半径内的元素值还没有被完全计算出来，它左边半径范围内的对称轴的对称半径是已经求出来的，并且左侧任何一个回文的右边界肯定没有C的右边界大，因为如果比C大那么这个C肯定不会出现。于是它所有的左侧的对称半径内的元素都在C的右边界之内，因为它最多能穿过对称轴C，而达不到C的右边界。但是除此之外还有C的右侧没算呢，所以按理来说它关于C对称的那个对称轴的左侧也包含了它的对称半径范围内的全部元素。现在假设B是C左侧半径范围内的一个对称轴，则B关于C对称的那个对称轴是D，但是D右侧边界如果超出了C的右边界，你就不能确保在C的对称半径长度内D包含的元素也和B的一样相同，你能确定的是D的对称半径至少是C的右边界减去D对称轴那么长，这就减少了些不必要的计算，于是此时你需要以D为C，重复上述计算。
如果它的对称半径小于，或者说在C的对称半径内，则D的半径就不需要再计算了，因为它可以由B的半径直接得到，因为D向两边扩展的遇到的第一对不同的字符还在C的对称半径之内。如果D的右边界恰好处在C右边界处，你也判断不出来D是否已经达到了D的最长回文子串，但是它的半径至少是当前这么长，这也减少了一些不必要的计算。然后你需要比对每一对字符，这就是一趟遍历了。
1、为什么它的时间复杂度是线性级别的？
你要是看代码绝对看不出来，累死你！
好，现在以只看代码的方式来看它的时间复杂度。首先映入眼帘的是一个for循环长度为2n+1，然后里面还有个while循环所以怎么想也都应该是O(n^2)吧，其实一开始我也是这么想的。
但是你要是看P数组的变化就会大概明白。C每次增长都是因为C内有一个D的右边界超出了C的右边界，于是才会引起while循环。而while循环又会确定新的C的右边界，并且while循环的次数就是新的C的右边界减去旧的C的右边界。至于说C半径内对称轴的对称半径的确定，只要没有让C的右边界得到扩展，那都是一次性确定的。由此从总体上看所有P所有值的确定都是一次性完成的，至于说其他的什么比较赋值什么的都是常数级别的，并且总量也是常数级别的，所以本算法时间复杂度是O(n)。
2、为什么不用担心关于对称轴对称的那个元素的下标为负的情况？
没关系，那只是一开始，并且马上会触发D的右边界超出了C的右边界的处理逻辑。而且从此以后再也不会出现为负的情况，因为它是在C的对称半径范围内，因为C是一个回文子串，所以它自然是有元素的，所以关于C对称的那个下标绝对不会是负数的。
实现
package com.company;
public class Main {
public static void main(String[] args) {
// write your code here
String inputString = "abcdasdfghjkldcba";
String inputString0 = "abbaabccba";
String inputString1 = "babad";
String inputString2 = "";
String inputString3 = null;
System.out.println(Solution.gainLongestPalindromicSubstring3(inputString1));
}
}
输出
bab
Process finished with exit code 0
代码实现
package com.company;
public class Solution {
/**
* 输出字符串中最长的回文。
* 回文就是正向看和逆向看都一样的字符串。
* 基于这一点我考虑使用正向字符串和反向字符串来解决这一问题
* 本来想用动态规划的思想解决的，但是没找准问题和子问题。
* 不过本算法如果遇到前后有对称字符串的时候就会给出错误解。
* 所以该方法是个错误解。
* 但是本算法是错误的实现，实际上它求出的是字符串中最长的对称子串。
* 但是只要再加上这个下标是不是一样就直到它是不是最长回文了。
* 不，你是要对得到的那个子串判断它是不是对称的。
* 这个方法比较麻烦。
* 时间复杂度已经在3次方级别了，姑且粗略表示为O(n^3)。
* 虽然它能得到正确结果，但是它已经严重超时了。
* 看来解决本题的思路是有问题的。
* 我想过的其他方法：
* 1、用栈，利用抵消操作来实现。
* 2、用字符串和它的逆串相对滑动来实现。
* 3、以某个点为圆心，用一个逐渐增长的半径来扫描。
* 我发现沿着自己脑中模糊的记忆中的解题路线来思考往往让自己陷入困境
* 因为它的关键点你并没有想全，而且由于是模糊的记忆所以导致可能解决
* 方案和题目是对不上的。
* @param sourceString
* @return
*/
static public String gainLongestPalindromicSubstring0(String sourceString) {
if (sourceString == null || sourceString.length() == 0)return "";
//首先翻转字符串
SingleLinker[][] answerArray = new SingleLinker[sourceString.length()][sourceString.length()];
SingleLinker longestPointer = null;
int longestCounter = 0;
for (int counter = 0;counter < sourceString.length();counter++) {
for (int counter0 = 0;counter0 < sourceString.length();counter0++) {
answerArray[counter][counter0] = new SingleLinker();
if (sourceString.charAt(counter) == sourceString.charAt(sourceString.length() - counter0 - 1)) {
if (counter - 1 >= 0 && counter0 - 1 >= 0) {
answerArray[counter][counter0].setCounter(1 + answerArray[counter - 1][counter0 - 1].getCounter());
answerArray[counter][counter0].prePointer = answerArray[counter - 1][counter0 - 1];
} else answerArray[counter][counter0].setCounter(1);
answerArray[counter][counter0].setReverseIndex(sourceString.length() - counter0 - 1);
answerArray[counter][counter0].setElementIndex(counter);
//这一步是关键
if (answerArray[counter][counter0].getCounter() > longestCounter) {
boolean isSymmetric = true;
SingleLinker tempHeader = answerArray[counter][counter0];
int endStartPlus = 2 * tempHeader.getElementIndex() - tempHeader.getCounter() + 1;
while (tempHeader != null && tempHeader.getCounter() > 0 && tempHeader.getElementIndex() >= endStartPlus / 2) {
if (sourceString.charAt(tempHeader.getElementIndex()) != sourceString.charAt(endStartPlus - tempHeader.getElementIndex())) {
isSymmetric = false;
break;
}
tempHeader = tempHeader.prePointer;
}
if (isSymmetric){
longestCounter = answerArray[counter][counter0].getCounter();
longestPointer = answerArray[counter][counter0];
}
}
}
}
}
for (int counter = 0;counter < sourceString.length();counter++) {
for (int counter0 = 0;counter0 < sourceString.length();counter0++) {
if (answerArray[counter][counter0].getCounter() != 0)
System.out.print(answerArray[counter][counter0].getCounter() + " ");
else System.out.print(" ");
}
System.out.println();
}
StringBuilder resultString = new StringBuilder();
while (longestPointer != null && longestPointer.getCounter() > 0) {
resultString.append(sourceString.charAt(longestPointer.getElementIndex()));
longestPointer = longestPointer.prePointer;
}
return resultString.toString();
}
/**
* 本算法采用的是动态规划算法。
* 动态规划算法的难点是如何找到具有关联关系的问题和子问题。
* 动态规划算法的数学模型是个分段函数。
* 回文子串的问题我就没发现问题和子问题是啥。
* 首先最低级的子问题就是每个字符是一个回文子串。
* 我所不解的问题是如何能够实现从前往后遍历不断判断回文子串。
* 很奇怪，如果头尾两边的元素不等那就不是一个回文子串，那为什么还要取大者？
* 问题可以归纳为如果一个子串已经是回文子串，那么它首尾相邻的元素相同就得到了一个更大的回文子串。
* 如果首尾相邻元素不相同，那么得到的这个回文子串就是当前最大的。
* 如果按照标准动态规划算法模板来解的话，那就应该是画表格求解。
* 于是应该有如果s[i]和s[j]相等则看它的左下角单元格是否是大于0的。
* 如果是就应该在s[i+1]和s[j-1]的基础上进行累加，也就是左下角的单元格的值的基础上进行累加。
* 如果左下角的单元格不大于0则代表没有必要再试探下去了，因为它已经不可能是回文了。
* @param sourceString
* @return
*/
static public String gainLongestPalindromicSubstring1(String sourceString) {
if (sourceString == null)return "";
int[][] answerSpace = new int[sourceString.length()][sourceString.length()];
int maxLength = 0;
int startIndex = -1;
for (int counter = sourceString.length() - 1;counter > -1;counter--) {
for (int counter0 = counter;counter0 < sourceString.length();counter0++) {
if (counter == counter0)answerSpace[counter][counter0] = 1;
else if (counter0 - counter == 1) {
if (sourceString.charAt(counter0) == sourceString.charAt(counter))
answerSpace[counter][counter0] = 2;
else answerSpace[counter][counter0] = 0;
} else {
if (sourceString.charAt(counter) == sourceString.charAt(counter0)) {
if (answerSpace[counter + 1][counter0 - 1] >= 1)
answerSpace[counter][counter0] = answerSpace[counter + 1][counter0 - 1] + 1;
else answerSpace[counter][counter0] = 0;
} else answerSpace[counter][counter0] = 0;
}
if (answerSpace[counter][counter0] >= 1 && counter0 - counter + 1 > maxLength) {
startIndex = counter;
maxLength = counter0 - counter + 1;
}
}
}
for (int counter = 0;counter < sourceString.length();counter++) {
for (int counter0 = 0;counter0 < sourceString.length();counter0++) {
System.out.print(answerSpace[counter][counter0] + " ");
}
System.out.println();
}
if (startIndex == -1 || maxLength == 0)
return "";
else return sourceString.substring(startIndex,startIndex + maxLength);
}
/**
* 中心轴轮转算法
* @param sourceString
* @return
*/
static public String gainLongestPalindromicSubstring2(String sourceString) {
if (sourceString == null && sourceString.equals(""))return "";
//中心轴的下标，如果是偶数代表轴是某字符，如果是奇数代表轴是间隙。
//先遍历轴。
int maxLength = 0;
int targetStartIndex = -1;
int targetEndIndex = -1;
for (int axisIndex = 0;axisIndex < 2 * sourceString.length();axisIndex++) {
if (axisIndex % 2 == 0) {
//此时代表中心轴是某个字符
int leftIndex = axisIndex / 2;
int rightIndex = leftIndex;
while (leftIndex > -1 && rightIndex < sourceString.length() && sourceString.charAt(leftIndex) == sourceString.charAt(rightIndex)) {
if (rightIndex - leftIndex + 1 > maxLength) {
maxLength = rightIndex - leftIndex + 1;
targetStartIndex = leftIndex;
targetEndIndex = rightIndex;
}
leftIndex--;
rightIndex++;
}
} else {
//此时代表中心轴是某个间隙
//对称轴左边的下标是axisIndex/2右边的下标是axisIndex/2+1，
// 左下标不要下越界，右下标不要上越界。
int leftIndex = axisIndex / 2;
int rightIndex = axisIndex / 2 + 1;
while (leftIndex >= 0 && rightIndex < sourceString.length() && sourceString.charAt(leftIndex) == sourceString.charAt(rightIndex)) {
if (rightIndex - leftIndex + 1 > maxLength) {
maxLength = rightIndex - leftIndex + 1;
targetStartIndex = leftIndex;
targetEndIndex = rightIndex;
}
leftIndex--;
rightIndex++;
}
}
}
if (targetEndIndex == -1 || targetStartIndex == -1)return "";
return sourceString.substring(targetStartIndex,targetStartIndex + maxLength);
}
/**
* 本算法应用manacher算法来实现。
* @param sourceString
* @return
*/
static public String gainLongestPalindromicSubstring3(String sourceString) {
if (sourceString == null)return "";
//这个是对称半径的数组。
int[] symmetricRadiusArray = new int[2 * sourceString.length() + 1];
//当前的右边界。
int currentRightEdge = 0;
//当前的中间对称轴。因为下标0对应的符号肯定没有对称半径，另外从1开始也能累加。
int currentCenterIndex = 0;
//用来记录最长回文对称轴的下标
int maxIndex = -1;
//用来记录最长回文的半径的长度
int maxRadius = 0;
//如果像网上讲的那样插入占位字符，就肯定解决不了sourceString如
// 果含有和站位字符相同的字符的问题。所以仅仅是在逻辑上插入一个占位字符吧。
// 推出总共有2n+1个字符。
// 其中偶数的下标是占位符，奇数的下标是字符串中的字符。
// 下标0可以直接跳过。因为[1,2 * sourceString.length())正好是有字符串中字符的范围。
for (int counter = 1;counter < 2 * sourceString.length();counter++) {
//首先找到对称的那个下标
int symmetricIndex = 2 * currentCenterIndex - counter;
//此时还没有来得及计算symmetricRadiusArray[counter]的值。
if (counter > currentRightEdge) {
//此时说明当前字符已经超过了半径范围了于是先置为0.
symmetricRadiusArray[counter] = 0;
} else {
//此时说明当前字符已经出右侧半径范围内了。
if (symmetricRadiusArray[symmetricIndex] <= currentRightEdge - counter) {
//此时说明它的对称半径至少是symmetricRadiusArray[symmetricIndex]
symmetricRadiusArray[counter] = symmetricRadiusArray[symmetricIndex];
} else {
//此时关于中心轴对称的字符的半径加上此时的counter已经超出了右边界的范围了。
// 于是最多能判定到右边界了。
symmetricRadiusArray[counter] = currentRightEdge - counter;
}
}
//但是此时的counter的对称半径并没有真正被判断出来，而只是最少状态，这个时候需要在其基础上继续扩展。
// 于是还需要while循环一下。由于我用的是逻辑占位符所以需要进行逻辑判断。
int leftIndex = counter - 1;
int rightIndex = counter + 1;
while (leftIndex > -1 && rightIndex < 2 * sourceString.length() + 1 && (leftIndex % 2 == 0 || sourceString.charAt(leftIndex / 2) == sourceString.charAt(rightIndex / 2))) {
symmetricRadiusArray[counter] = rightIndex - counter;
leftIndex --;
rightIndex ++;
}
//如果此时counter加上它真正的对称半径大于了当前的右边界，就说明应该更新了。
if (counter + symmetricRadiusArray[counter] > currentRightEdge) {
currentCenterIndex = counter;
currentRightEdge = currentCenterIndex + symmetricRadiusArray[counter];
if (symmetricRadiusArray[counter] > maxRadius) {
maxRadius = symmetricRadiusArray[counter];
maxIndex = counter;
}
}
}
//现在就要看最后的结果了
if (maxIndex == -1 || maxRadius == 0)return "";
else {
StringBuilder result = new StringBuilder();
int resultStringLength = 2 * maxRadius + 1;
int startIndex = maxIndex - maxRadius + 1;
for (int counter = startIndex;counter < startIndex + resultStringLength - 1;counter += 2)
result.append(sourceString.charAt(counter / 2));
return result.toString();
}
}
}
package com.company;
public class SingleLinker {
public SingleLinker prePointer = null;
private int counter = 0;
private int elementIndex = -1;
private int reverseIndex = -1;
public SingleLinker() {
}
public int getCounter() {
return counter;
}
public void setCounter(int counter) {
this.counter = counter;
}
public int getElementIndex() {
return elementIndex;
}
public void setElementIndex(int elementIndex) {
this.elementIndex = elementIndex;
}
public int getReverseIndex() {
return reverseIndex;
}
public void setReverseIndex(int reverseIndex) {
this.reverseIndex = reverseIndex;
}
}
网友评论