一、题目
最长回文子串：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd” 输出: “bb”
二、我的答案
思路
1. 排除法，最优解法肯定不是暴力遍历 2. 紧接着想到第三题中使用的两个指针同步遍历一个字符串的方法，尝试了一下，发现跟暴力遍历没有区别 3. 再看几遍题，要找的是回文字符串，回文字符串的特点在于两边字符都相同，也就是说需要找的是两边字符都相同中间点(注意是中间点而不是中间字符，因为题干中例 1 的中间点是 a，但是例 2 的中间点是 bb)
代码
v1.0(过于丑陋，可跳过直接看说明和 v2.0)
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
function expendString(index1, index2) {
if(index1 > 0 && index2 + 1 < s.length &&s[index1 -1] === s[index2 + 1]){
return expendString(index1 -1, index2 + 1)
} else {
return [index1, index2, index2 – index1]
}
}
let longestArr = [0, 0, 0]
let tempArr
for(let i = 1; i< s.length; i++) {
if(i + 1 < s.length&&s[i-1] === s[i+1]) {
tempArr = expendString(i-1, i+1)
tempArr[2] > longestArr[2] ? longestArr = tempArr : null
}
if(s[i -1] === s[i]) {
tempArr = expendString(i – 1, i)
tempArr[2] > longestArr[2] ? longestArr = tempArr : null
}
}
return s.slice(longestArr[0], longestArr[1] + 1)
};
讲解
1. 函数 expendString 作用为以两个传参拓展字符串，判断是否依然是回文字符串
2. 数组 longestArr 作用为防止当前最长字串的两个下标和长度(我也不知道当时自己为什么还要费劲写个数组)
3. for 循环中判断回文串的中点是一个 (‘aba’) 还是两个(‘abba’), 然后分别调用上文定义的 expendString 函数进行拓展
通过，下一步要做的就是优化成能看懂的版本
v2.0
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s){
function expendString(index1, index2) {
if (index1 >= 0 && index2 < s.length && s[index1] === s[index2]) {
expendString(index1 – 1, index2 + 1)
} else {
index2 – index1 > longestString.length ?
longestString = s.slice(index1 + 1, index2) :
null
}
}
let longestString = s[0] || ”
for (let i = 1; i < s.length; i++) {
if (i + 1 < s.length) {
expendString(i – 1, i + 1)
}
if (s[i – 1] === s[i]) {
expendString(i – 1, i)
}
}
return longestString
};
三、优秀答案
to be continued
四、路漫漫其修远兮