原题地址：最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
暴力解法
找出所有的子串，依次判断是否是回文串即可：
/**
* @param {string} s
* @return {string}
*/
const longestPalindrome1 = function(s) {
if (s.length < 2) {
return s;
}
/**
* 判断子串是否为回文串
* @param start 子串的开始位置
* @param length 子串的长度
* @returns {boolean} 是否为回文串
*/
const isPalindrome = (start, length) => {
if (length < 2) {
return true;
}
for (let i = start; i < start + length / 2; i ++) {
if (s[i] !== s[length + 2 * start - i - 1]) {
return false;
}
}
return true;
};
let [result, max] = ['', 0]; // 最长回文子串及其长度
for (let i = 0; i < s.length; i ++) {
// 只有长度大于max的子串才需要判断
for (let j = i + max; j < s.length + 1; j ++) {
if (isPalindrome(i, j - i)) {
[max, result] = [j - i, s.substr(i, j - i)];
}
}
}
return result;
};
测试：
let start = new Date();
const test = longestPalindrome1;
console.log(test('babad')); // abc
console.log(test('abcda')); // a
console.log(test('cbbd')); // bb
console.log(test('babadada')); // adada
console.log(test('ccc')); // ccc
console.log(new Date().getTime() - start.getTime()); // 4
时间复杂度： 找到子串需要双重遍历，判断子串是否是回文串还需要一次遍历，所以时间复杂度为O($n^3$)
空间复杂度： 不需要额外的存储空间，空间复杂度为O(1)
递归算法
暴力解法中判断是否是回文串的部分，我们可以考虑用递归的方法来实现。因为判断一个字符串是否是回文串我们可以分解为两个部分，即先判断端点的两个字符是否相等，再判断剩下的部分是否是回文串。这样就可以很清楚地改写为递归：
/**
* @param {string} s
* @return {string}
*/
const longestPalindrome2 = function(s) {
if (s.length < 2) {
return s;
}
/**
* 判断子串是否为回文串
* @param start 子串的开始位置
* @param length 子串的长度
* @returns {boolean} 是否为回文串
*/
const isPalindrome = (start, length) => {
if (length < 2) {
return true;
}
return s[start] === s[start + length - 1] && isPalindrome(start + 1, length - 2);
};
let [max, result] = [0, '']; // 最长回文子串及其长度
for (let i = 0; i < s.length; i ++) {
// 只有长度大于max的子串才需要判断
for (let j = i + max; j < s.length + 1; j ++) {
if (isPalindrome(i, j - i)) {
[max, result] = [j - i, s.substr(i, j - i)];
}
}
}
return result;
};
测试：
let start = new Date();
const test = longestPalindrome2;
console.log(test('babad')); // abc
console.log(test('abcda')); // a
console.log(test('cbbd')); // bb
console.log(test('babadada')); // adada
console.log(test('ccc')); // ccc
console.log(new Date().getTime() - start.getTime()); // 4
时间复杂度： 递归判断是否是回文串时时间复杂度为O(n),所以整体时间复杂度与暴力法相同，为O($n^3$)
空间复杂度： 递归所需要的空间复杂度为O(n)，但每一次判断是否为回文串时的递归是独立的，所以整体空间复杂度也是O(n)
动态规划
仔细考虑上面的递归算法，会发现我们进行了相当多的重复计算。判断一个子串是否为回文串的计算，我们在包含它的更大的子串判断时都会要重复计算。如abcba中，判断c是否是回文串的计算过程，我们在判断bcb和abcba时都需要重复进行。
既然如此，我们就可以将这些计算结果保存下来，在更长子串的判断需要用到这些结果时直接查询即可。这就是所谓的动态规划，相当于对递归算法进行空间换时间的优化。
思路清楚后，代码也就很容易写了：
/**
* @param {string} s
* @return {string}
*/
const longestPalindrome3 = function(s) {
if (s.length < 2) {
return s;
}
let [left, max] = [0, 1]; // 最长回文子串的左边界和长度
// 二维数组，用来存储所有的子串是否为回文串
// array[i][j] = true 表示s.subStr(j,i+1)为回文串
let array = new Array(s.length);
// 把长度为1和2的回文串的判断也写到了一起
for (let i = 1; i <= s.length; i ++ ) {
// 长度为i的子串有s.length-i+1个
array[i - 1] = new Array(s.length - i + 1);
for (let j = 0; j < s.length - i + 1; j ++) {
// 长度为1和2的回文串判断是基础，只需要判断端点即可
if (s[j] === s[j + i - 1] && (i < 3 || array[i - 3][j + 1])) {
array[i - 1][j] = true;
if (i > max) {
[left, max] = [j, i];
}
}
}
}
return s.substr(left, max);
};
测试：
let start = new Date();
const test = longestPalindrome3;
console.log(test('babad')); // abc
console.log(test('abcda')); // a
console.log(test('cbbd')); // bb
console.log(test('babadada')); // adada
console.log(test('ccc')); // ccc
console.log(new Date().getTime() - start.getTime()); // 3
时间复杂度： 双重遍历，时间复杂度为O($n^2$)
空间复杂度： 需要一个额外的二维数组来存储回文串的判断情况，空间复杂度为O($n^2$)
中心扩展算法
递归和动态规划都是利用回文串的特点，将一个回文串的判断逐步拆解为更小子串的判断。实际上我们也可以将这一过程反过来，从最小的子串开始，逐步向外扩展，找到更长的回文子串，这就是中心扩展算法。
如果一个子串是回文串，只要它左右两边的字符相等，那么扩展一位得到的也必然是回文串。例如字符串abcbd，子串c是回文串，左右两边都是字符b，所以扩展一位得到的子串bcb也是回文串，但bcb左右两边的a和d不相等，所以扩展得到的子串abcbd就不是回文串。
只要以每一个可能的回文串中心依次向外扩展，就可以得到所有的回文子串。注意这样的中心有2n+1个，因为两个字符的中心也可能是回文串的中心，如回文串bccb的中心就在两个字符c中间。具体实现如下：
/**
* @param {string} s
* @return {string}
*/
const longestPalindrome4 = function(s) {
if (s.length < 2) {
return s;
}
/**
* 中心扩展
* @param left 左边界
* @param right 右边界
* @returns {number} 扩展得到的最长回文子串的长度
*/
const centerSpread = (left, right) => {
// 只需要判断left的边界，如果right越界了s[left]===s[right]会返回false
while (left >= 0 && s[left] === s[right]) {
left --;
right ++;
}
return right - left - 1;
};
let [left, max] = [0, 0]; // 最长回文子串的起点和长度
for (let i = 0; i < s.length; i ++) {
// 取i相关的两个中心扩展得到的回文子串较长的一个
let length = Math.max(centerSpread(i, i), centerSpread(i, i + 1));
if (length > max) {
[left, max] = [i - Math.floor((length - 1) / 2), length];
}
}
return s.substr(left, max);
};
测试：
let start = new Date();
const test = longestPalindrome4;
console.log(test('babad')); // abc
console.log(test('abcda')); // a
console.log(test('cbbd')); // bb
console.log(test('babadada')); // adada
console.log(test('ccc')); // ccc
console.log(new Date().getTime() - start.getTime()); // 3
时间复杂度： 找到每个中心需要一次遍历，从中心扩展时又需要一次遍历，时间复杂度为O($n^2$)
空间复杂度： 不需要额外的存储空间，空间复杂度为O(1)
Manacher算法
本题还有一个效率更高的解法，Manacher算法，又称为马拉车算法，可以在线性时间内解决最长回文子串的问题，是由一个叫Manacher的人在1975年发明的。
这个算法的思想与中心扩展算法类似，但经过了进一步优化以减少重复计算。我们可以分为三步来理解它。
改造原字符串
在中心扩展算法中，我们寻找回文串时，需要对奇数和偶数长度的回文串分开考虑。现在我们可以通过添加特殊字符的方式，将两种情形统一起来。
具体的实现就是在所有字符间以及字符串的两端添加统一的特殊字符，这个字符 要在原字符串中不存在，这里面用#。如原字符串abc（记为S）改造后就成了新字符串#a#b#c#（记为T），这样长度n的字符串改成后的长度就是2n+1，固定成为了奇数。
回文半径
回文半径指的是新字符串中每个字符所在的回文子串最右端到当前字符的距离，由新字符串T的每个字符的回文半径构成的数组称为回文半径数组，记为P。例如字符串babadada改造后的字符串为#b#a#b#a#d#a#d#a#，对应的回文半径数组P如下表所示：
|index|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |T|#|b|#|a|#|b|#|a|#|d|#|a|#|d|#|a|#| |P|1|2|1|4|1|4|1|2|1|4|1|6|1|4|1|2|1|
通过对比，我们会发现原字符串中字符S[i]所在回文子串的长度 = P[i] - 1。因为新字符串中加了特殊字符后并不会影响原来的回文特性，如adada变成#a#d#a#d#a后，回文子串的长度必然变成2n+1，回文半径就是n+1，所以P[i]-1就是原字符串对应回文子串的长度。这样我们的问题就转变成了求回文半径数组P。
求回文半径数组P
从左往右计算数组P，将当前最靠右的回文子串的中心和左右边界分别标记为mc和ml、mr：
- i<mr，意味着i还在当前最大回文子串的范围之内。利用回文串对称的特点，我们可以找到i关于mc的对称点，记为j，j=2*mc-i。i和j都在最大回文子串[ml,mr]的范围内：
- P[j]<mr-i，由回文串的对称性可知mr-i=j-ml，所以P[j]<j-ml，即j所在的回文子串没有超出最大回文子串的范围，由对称性可知，P[i]=P[j]。
- P[j]>=mr-i，即j所在回文子串已经超过了最大回文子串的范围，此时P[i]与P[j]不在一定相等。但由对称性可知，i所在回文子串的右端不会小于最大回文子串的右端，即P[i]>=mr-i,所以我们可以直接从mr+1开始匹配。
- i>=mr，不能利用回文串的特性，需要正常匹配。
这就是Manacher算法的思想，具体的实现如下：
/**
* @param {string} s
* @return {string}
*/
const longestPalindrome5 = function(s) {
if (s.length < 2) {
return s;
}
// 改造原字符串，加上特殊字符#
let t = '#';
for (let i = 0; i < s.length; i ++) {
t = `${t}${s[i]}#`
}
t += '&'; // 最后再加一个特殊字符，可以保证通过中心扩展查找回文串时能正常结束
/**
* 中心扩展，找到回文串的最右端
* @param center 回文串的中心位置
* @param right 初始最右端
* @returns {*} 扩展后的最右端
*/
const centerSpread = (center, right) => {
let r = right;
while (t[r] === t[2 * center - r]) {
r ++;
}
return r;
};
let [mc, mr] = [0, 0]; // 当前最靠右的回文子串的中心和右端位置
let [center, max] = [0, 0]; // 找到的最大回文半径及其位置
let p = new Array(t.length); // 回文半径数组
for (let i = 0; i < t.length; i ++) {
// 以下部分的逻辑与上文保持一致
if (i < mr) {
let j = 2 * mc - i;
if (p[j] < mr - i) {
p[i] = p[j];
} else {
[mc, mr] = [i, centerSpread(i, mr)];
p[i] = mr - i;
}
} else {
[mc, mr] = [i, centerSpread(i, i + 1)];
p[i] = mr - i;
}
if (p[i] > max) {
[center, max] = [i, p[i]];
}
}
return s.substr((center - max + 1) / 2, max - 1)
};
测试：
let start = new Date();
const test = longestPalindrome5;
console.log(test('babad')); // abc
console.log(test('abcda')); // a
console.log(test('cbbd')); // bb
console.log(test('babadada')); // adada
console.log(test('ccc')); // ccc
console.log(new Date().getTime() - start.getTime()); // 3
时间复杂度： 只需要一次遍历，通过中心扩展查找回文子串时已经找过的不需要再找，所以总的时间复杂度为O(2n) = O(n)
空间复杂度： 需要一个改造后的字符串和一个回文半径数组，都是O(n)，所以总空间复杂度也是O(n)
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 27,2019