题目描述
leetcode地址
给定一个字符串 ，找到其最长的回文子串，回文的意思是，将字符翻转后仍为原字符。
例：输入abcbd，输出：bcb
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
// Your code
}
方法一：中心扩散法
分析：回文字符的特点是以某个字符为对称点，其两侧对应位置的字符相同，要注意如果中心字符串是偶串，则需要特殊处理，不能直接往两边扩散，比如abccbd，若以c为中心往两边扩散没有考虑其是偶串，就得不到正确结果。
图示：
屏幕快照 2019-12-29 下午6.54.20.png
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let size = s.length
if(size <= 1) return s
if(size === 2) return s[0] === s[1] ? s : s[0]
let palindromicStr = ''
for(let i = 1; i < size-1; i++) {
let left = i-1, right = i+1;
let temp = s[i]
while(left >= 0 && s[left] === s[i]) {
temp += s[left]
left--
}
while(right < size && s[right] === s[i]) {
temp += s[right]
right++
}
while(left >= 0 && right < size) {
if(s[left] !== s[right]) break;
temp = s[left] + temp + s[right]
left--
right++
}
if(temp.length > palindromicStr.length) {
palindromicStr = temp
}
}
return palindromicStr
};
时间复杂度：O(n^2)
空间复杂度：O(n)
截屏2021-02-04 14.03.48.png
方法二：扩展字符的中心扩散法
上面的代码中，有两个额外的while循环，它们处理的是当中心字符是偶串的场景。
while(left >= 0 && s[left] === s[i]) {
temp += s[left]
left--
}
while(right < size && s[right] === s[i]) {
temp += s[right]
right++
}
如果在每个字符间都插入一个特殊字符，就能处理所有的场景，如图：
截屏2021-02-05 11.35.51.png
如果中心字符是奇数，那么中心元素就是它本身，如果中心字符是偶串，那么中心元素是插入的特殊符号。不管是什么，总之都不用考虑中心元素是偶串还是奇串了。
代码实现：
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let size = s.length
if(size <= 1) return s
let str = '#'
for(let i = 0; i < size; i++) {
str += s[i] + '#'
}
size = str.length
let min = 0, max = 0
for(let i = 1; i < size-1; i++) {
let left = i-1, right = i+1;
while(left >= 0 && right < size) {
if(str[left] !== str[right]) break;
left--
right++
}
if(right-left > max-min) {
max = right-1
min = left+1
}
}
// 映射回原字符的索引
min = Math.floor((min)/2)
max = Math.ceil((max-1)/2)
return s.slice(min, max)
};
时间复杂度：O(n^2)
空间复杂度：O(n)
截屏2021-02-05 14.15.08.png
方法三：动态规划法
思路：利用空间换时间，即对于字符串abcba，如果已经知道bcb是回文字符串，那么abcba是回文字符串仅需满足字符串的首尾元素相同。
用二维数组dp[i][j]存储状态，(i, j)表示回文字符串的起始和结束位置。
由此写出状态转移方程：
dp[i][j] = dp[i+1][j-1] && s[i] === s[j]
翻译过来就是一个起始位置是i, 结束位置是j（包含i, j处的字符）的子串是回文子串的条件是起始位置是i+1, 结束位置是j-1的子串是回文子串且i位置的字符和j位置的字符相同。
另外注意一点，由于 i是起始位置，j是结束位置，则i < j始终成立。这也意味着，对于dp[i][j]，对角线以下部分的值不用考虑，那对角线代表的意思呢？很明显，就是起始位置等于结束位置的字符，其一定是回文。那么可以写出dp数组的初始状态：
var longestPalindrome = function(s) {
let dp = [], size = s.length
for(let i = 0; i < size; i++) {
dp[i] = []
}
for(let i = 0; i < size; i++) {
dp[i][i] = true;
}
}
以下图中的字符为例，s = abccbd，
第一行每一列的值表示起始位置是0，结束位置是j的字符是否是回文
第二行每一列的值表示起始位置是1，结束位置是j的字符是否是回文
...
截屏2021-02-25 16.29.03.png
这里还有一个规律，前面说了，若子串长度是1，则一定是回文，那么若子串长度是2呢？只要满足s[i] === s[j]，子串就是回文。
/**
* 方法三：动态规划
* 时间复杂度：O(n^2) 空间复杂度：O(n^2)
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let dp = [], size = s.length
let start = 0, end = 0;
for(let i = 0; i < size; i++) {
dp[i] = []
}
for(let i = 0; i < size; i++) {
dp[i][i] = true;
}
for(let j = 1; j < size; j++) {
for(let i = 0; i < j; i++) {
dp[i][j] = j-i === 1 ? s[i] === s[j] : dp[i+1][j-1] && s[i] === s[j]
if(dp[i][j] && (j-i > end - start)) {
end = j
start = i
}
}
}
return s.slice(start, end+1)
}
屏幕快照 2021-02-28 下午5.49.45.png
可以看到，由于动态规划本来的好处是以空间换时间以降低时间复杂度，但这里动态规划的性能反而是最差的，不过这也是因为回文子串的特点清晰容易找到捷径，在大部分情况下动态规划表现都是很不错的。
最后
寻找回文子串还有一个方法叫Manacher算法，也就是俗称的马拉车算法，此算法着实绕，我看了多次也是稀里糊涂的，我选择放弃。
网友评论