HJ85 最长回文子串
题目描述
示例
代码
代码1 暴力求解，遍历出所有子字符串，判断是否为回文
js
/*
求一个字符串中 最长回文子串（中心对称，正反都一样）
1. 暴力解法
显然 一个 字符 就是一个回文
所以应该枚举 所有 长度 大于 2 的子串，判断是否为回文
最后输出 最长的回文
判断回文的时候，可以只判断比当前长度大的是否为回文，作为一个优化点
（因为题目说的只需要输出最大回文的长度）
*/
let readline = require('readline')
let rl = readline.createInterface({
input: process.stdin,
output: process.stdout
})
rl.on('line', line=>{
let len = line.length // 输入字符串的长度
if(len === 1){ // 如果就一个字符。直接输出1
console.log(1)
}else {
let maxLen = 1 // 默认当前最大回文长度为1
// 枚举出所有长度大于2 的子串，判断是否为回文
for(let i = 0; i < len - 1; i++){
for( let j = i + 1; j < len; j++ ){
let s = line.slice(i, j+1) // 截取当前子串，判断是否为回文
// 优化，只判断长度比当前最大回文长度大的子串
if( s.length > maxLen && isCircleString(s) ){
maxLen = s.length
}
}
}
console.log(maxLen)
}
})
// 判断字符串是否为回文
function isCircleString(s){
let result = true // 默认为false
let i = 0
let j = s.length - 1
while( i < j ){
if(s[i] === s[j]){
i++
j--
} else {
result = false
break
}
}
return result
}代码2 中心扩散法
js
/*
求一个字符串中 最长回文子串（中心对称，正反都一样）
1. 中心扩散法，尽可能的往两边扩散
奇数中心是个数
偶数个中心是个缝
*/
let readline = require('readline')
let rl = readline.createInterface({
input: process.stdin,
output: process.stdout
})
rl.on('line', line=>{
let len = line.length
if(len === 1){
console.log(1)
}else {
let maxLen = 1
// 中心枚举到 len - 2 即可（因为最后一位不用扩散了）
for ( let i = 0; i < len - 1; i++ ) {
let oddStr = centerSpread(line, i, i)
let evenStr = centerSpread(line, i, i+1)
let maxStr = oddStr.length > evenStr.length ? oddStr : evenStr
if(maxStr.length > maxLen){
maxLen = maxStr.length
}
}
console.log(maxLen)
}
})
/*
中心扩散
如果left === right 回文中心是个缝 回文串的长度是 奇数
right = left + 1 的时候，此时回文中心是任意一个字符，回文串的长度是偶数
*/
function centerSpread(s, left, right){
let len = s.length
let i = left
let j = right
while( i >= 0 && j < len ){
if( s[i] === s[j] ){
i--
j++
} else {
break
}
}
return s.slice( i + 1, j )
}